[伯俊/C+]11053号最長の部分数列を追加

13927 ワード
DP 白駿 テキストリンク

問題は次のとおりです.

まず,グローバル配列d[n]においてn番目の項に達したときの最長増分数列の項数を考える.
上記の例で見ると、
10 20 10 30 20 50.
  • 第1のケースは10−>d[1]=1(自己)
    • である.
  • 第2のケースは10,20->d[2]=2
    • である.
  • 第3のケースは10->d[3]=1である
    ...
    • このまま
    ここで見たいのは.
    n回d[n]を求めるために、前の1回から~n-1回回り(本文の2番目の変数jを参照)
    増分数列を求めるので,以前のa[j]彼らのd[j]+1(1現在n個の自己を加えた)はd[i]のすべての値である.
    つまり、j回りに回って、毎回比較的高い値で更新すればいいのです.
    これに対する論理は次のプロセスです.
          cin>>tmp;
      a[i]=tmp;
      d[i]=1;

      for(int j=i-1; j>=1; j--){ // 앞에 항들 점검
        if(a[j]<a[i]){ // 항이 현재 항보다 작다면-> 증가 수열 조건 성립
          d[i]=max(d[i], d[j]+1); // d[i]가 될 수 있는 값들 중 최댓값 매번 갱신하기
        }
      }
    最も重要な部分はこの部分です
    最初,問題が容易に解決できない部分は,a[j]の値がa[i]より小さく,その中で最大のa[j]のみが要求され,d[i]がd[j]+1であると考えられる.
    しかし,これは最大のa[j]を求めているのではなく,最大のd[j]値を持つa[j]を求めているとずっと考えていた.
    私のすべてのコードは次のとおりです.
    #include <bits/stdc++.h>
using namespace std;

int a[1001]={0, };
int d[1001]={0, };

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, tmp, res;
    cin>>n;
    cin>>tmp;
    a[1]=tmp;
    d[1]=1;
    res=1;

    for(int i=2; i<=n; i++){
      cin>>tmp;
      a[i]=tmp;
      d[i]=1;

      for(int j=i-1; j>=1; j--){
        if(a[j]<a[i]){
          d[i]=max(d[i], d[j]+1);
        }
      }

      res=max(res, d[i]);
    }

    cout<<res<<endl;
    return 0;
}
    2月8日火曜日復習)
    #include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int a[1001]={0, }; int dp[1001]={0, };
    int tmp, len, res=1, n; cin>>n;
    
    for(int i=0; i<n; i++){
      cin>>tmp; a[i]=tmp; len=1;
      for(int j=i-1; j>=0; j--){
        if(a[j]<a[i] && dp[j]+1>len) len=dp[j]+1;
      }
      dp[i]=len;
      res=max(res, dp[i]); // 가장 긴 길이 계속해서 갱신
    }

    cout<<res<<"\n";
    return 0;
}
    Hexoでgithuで個人ブログを作る
    9月14日(月)レスポンス-カスタムコンポーネント(CSS)