Javaを使用してLISアルゴリズムを実装し、フォーメーション形成の問題を解決します

シーケンス 2,1,3,5 があるとします。最長の昇順サブシーケンスは 2,3,5 または 1,3,5 で、どちらも長さは 3 です。

LIS アルゴリズムの考え方は次のとおりです:

シーケンス a があると仮定します。

① 要素が 1 つしかない場合、最長の昇順部分列の長さは 1 です。

② 要素が 2 つある場合、a[1]>a[0] の場合、最長の昇順部分列の長さサブシーケンスは 2 です。a[1] は最長の昇順サブシーケンスの最後の要素です。a[1]

③ 要素が 3 つある場合、a[2]>a[0]、a[2]>a[1] の場合、a[2] は a[0] または a[ の位置になります。 1] 最長の昇順サブシーケンスの最後の要素。どのシーケンスを選択するかは、a[0] または a[1] がどちらのシーケンスに位置するかによって異なります。

④ n 要素への拡張は、a[n] を最後の要素とする最長の昇順サブシーケンスの長さを確認することです。

2 つの配列を定義します。1 つは a で、もう 1 つは b です。

a は元のデータを格納し、b[i] は a[i] で終わる最長の昇順サブシーケンスの長さを格納します。

コードは次のとおりです:

class Lmax{
    
  public static void Lmax(int[] a,int[] b){
      
    b[0]=1;             
          
    for(int i=1;i<a.length;i++){
      int countmax=0;
      for(int j=0;j<i;j++){
        if(a[i]>a[j]&&b[j]>countmax){ 
          countmax=b[j];   //记录下元素数值比a[i]小的但是对应子序列最长的子序列长度
        }
      }
        
      b[i]=countmax+1;     //a[i]对应的最长子序列长度是
    }
          
  }
    
}

2. 運動のフォーメーション

問題の説明:

私が高校にいたとき、学校は毎朝、命令が来るたびに学校の教師と生徒全員を組織して運動をさせました。運動をするという音が鳴り、私は全員が階下に走り始めました。すると、背の低い人は列の前に並び、背の高い人は後ろに並ばなければなりませんでした。ある日突然、演習の責任者がアイデアを思いつき、陣形を変更したいと考えました。つまり、全員が階段を駆け下りた後、全員がランダムに一列に配置され、その後に責任者が配置されました。演習はチームから抽出されたもので、チーム内の残りの生徒の身長が前から後ろから見ると「頂点」の形に見える場合があります。この形はすべての人に幸運をもたらすと言われており、あなたの学業の成功を祈ります。 (1、1、2、2、1 がすべて条件を満たすなど、山の片側だけが条件を満たすことに注意してください)

入力:

入力には複数のテスト サンプルが含まれる場合があります。
各テスト ケースの入力の最初の行は、入力される生徒の数を表す整数 n (1<=n<=1000000) です。
入力の 2 行目には、生徒の身長 (cm) を表す n 個の整数が含まれています (身長は 200 以下の正の整数です)。

出力:

各テストケースに対応して、抽出する必要がある生徒の最小数を出力します。

サンプル入力:

6

100 154 167 159 132 105

5

152 152 152 152 152

サンプル出力:

0

4

私はこの問題を解決するために LIS を使用しています。これについては次のようになります:

まず、LIS を使用して、各要素で終わる最長の昇順のサブシーケンスの長さを前から後ろに見つけます。次に、配列の順序を逆にして、LIS を使用して、各要素で終わる最長の昇順のサブシーケンスを見つけます。要素。シーケンスの長さ。

2 つの配列 b1、b2 を取得します。

B1 と b2 は、繰り返されたものの加算と減算に対応し、最も長い「山」になります。

public class peak {
    
  public static void main (String[] args)
  {
    int n; 
    int re;
    do{
      Scanner in = new Scanner(System.in);
      n = in.nextInt();
    }while(n<0||n>100000);
      
    int []a = new int[n];           //原始数组
    int []ar = new int[n];          //逆序数组
    Scanner in = new Scanner(System.in);
      
    for(int i=0;i<n;i++){
      a[i]=in.nextInt();
    }     
    int[] b1 = new int[n];
    @SuppressWarnings("unused")
    int[] b2 = new int[n];
    Lmax.Lmax(a, b1);
    ar=reverse.reverse(a);     
  
    Lmax.Lmax(ar, b2);       //求解逆序数组的最长上升子序列
  
    b2=reverse.reverse(b2);     //将逆序数组的最长上升子序列逆序以便和原始数组的最长上升子序列对应相加
      
    re = result.result(b1, b2);
    System.out.print(re);
  }
  
}<br><br><br><br>

class result{
  public static int result(int[] a,int[] b){
    int max=0;
    int[] c = new int[a.length];
    for(int i=0;i<a.length;i++){
      c[i]=a[i]+b[i];
    }
    Arrays.sort(c);
    max=c[c.length-1]-1;    //对应相加最长的再减去重复的一个人
    return a.length-max;
  }
}

上記は、エディターが提供した、Java を使用して LIS アルゴリズムとフォーメーションを実装する問題の全内容です。PHP 中国語 Web サイトをサポートしてください。

さらに Java を使用して実装してください。 LIS アルゴリズム、ドリル形成の問題に関する関連記事については、PHP 中国語 Web サイトにご注意ください。