配列配列-最長上昇サブシーケンス

2021 ワード

タイトルの説明:
整数配列を与え,この配列の最長厳格な増分サブシーケンスの長さを求める.例えば、シーケンス1 2 2 4 3の最長厳格増分サブシーケンスは、1,2,4または1,2,3である.彼らの長さは3です.
入力:
入力には、複数のテストケースが含まれる場合があります.各テストケースについて、入力される第1の動作の整数n(1<=n<=10000000):入力するシーケンスの長さを表す第2の行には、この配列の数値を表すn個の整数が含まれる.整数はintの範囲内です.
出力:
各テストケースについて、最長厳格なサブシーケンス長を出力します.
サンプル入力:

サンプル出力:

2
1

古いテーマで、ネット上には古典的なnlognのアルゴリズムがありますが、それは書きにくいです.2点になると書き間違えやすい.数状配列を使っていますが、手順が多いです.
まず離散化して入力したデータを再番号付けし、
例えば10,20,30
0 1 2になりました.
最長上昇サブシーケンス長は相対サイズにのみ関係するため,結果には影響しない.
次は前から後までDPです.
統計値は、現在の要素の末尾にある最大上昇サブシーケンスの長さです.
dpと記すと、本来O(n*n)アルゴリズムではすべての0からi-1のDP値をスキャンし、本質的にはi番目の位置の前にaより要素が小さく、最大値DPがいくらであるかを解く.ここでは、これを木の配列で作ることができます.aより小さいこのセグメントの最大値がどれくらいなのかを調べればいいです.そして、現在のDP値を配列中のaの位置に挿入する.
私はSTLをいくつか使ったので、書くのもそんなに長くありません.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long lld;
const int MAX=110000;
 
const int INF=1000000000;
int a[MAX];
int dcre[MAX];
int tree[MAX];
int query(int t)
{
       int ret=0;
       while(t)
       {
              if(tree[t]>ret)ret=tree[t];
              t-=(-t)&t;
       }
       return ret;
}
void ins(int t,int v,int m)
{
       while(t<=m)
       {
              if(v>tree[t])tree[t]=v;
              t+=(-t)&t;
       }
}
//start  ： ， 。
int main()
{  
       int T;
       int n,m;
       int last=0;
       int i,j,k;
      
       while(scanf("%d",&n)!=EOF)
       {
              for(i=0;ians)ans=tmp;
                     ins(a[i],tmp,m);
              }
              printf("%d
",ans);
       }
    return 0;
}

[Jobdu]タイトル1510:スペースの置換

Laravelユニットテスト