NOIP 2004コーラスキュー

三、合唱隊形
(chorus.pas／dpr／c／cpp)
【問題の説明】
N人の学生が一列に並んで、音楽の先生はその中の(N-K)人の学生に列を作ってもらって、残りのK人の学生が合唱の隊形に並ぶようにします.
合唱隊形とは、K人の同級生を左から右に順に1,2...,Kとし、彼らの身長はそれぞれT 1,T 2,...,TKであれば、彼らの身長はT 1<...>を満たす隊形である.Ti+1>…>TK(1<=i<=K).
あなたの任務は、すべてのN人の同級生の身長を知っていて、少なくとも何人の同級生が列に並ぶ必要があることを計算して、残りの同級生を合唱の隊形に並べることができます.
【入力ファイル】
入力ファイルinの最初の行は整数N(2<=N<=100)であり、同級生の総数を表す.1行目にはn個の整数があり、スペースで区切られ、i番目の整数Ti(130<=Ti<=230)はi番目の同級生の身長(センチメートル)である.
【出力ファイル】
出力ファイルoutには1行が含まれています.この行には1つの整数しか含まれていません.つまり、少なくとも何人かの同級生が列を出す必要があります.
【サンプル入力】
8
186 186 150 200 160 130 197 220
【サンプル出力】
4
【データ規模】
50%のデータに対して、n<=20が保証されている.
すべてのデータに対して、n<=100が保証されます.
 
【考え方】
リニアDP.                                        
正逆に各1回の最長厳格上昇サブシーケンスを求めてd[]g[]を得,最高点まで列挙することで残りの人数の最大値を得ることができる.
 
【コード】

 1 #include
 2 using namespace std;
 3 
 4 const int maxn = 100+10;
 5 int d[maxn],g[maxn],A[maxn];
 6 int n;
 7 
 8 int main() {
 9     ios::sync_with_stdio(false);
10     cin>>n;
11     for(int i=0;i>A[i];
12     for(int i=0;i) {
13         d[i]=1;
14         for(int j=0;jif(A[j]<A[i])
15          d[i]=max(d[i],d[j]+1);
16     }
17     for(int i=n-1;i>=0;i--) {
18         g[i]=1;
19         for(int j=i+1;jif(A[i]>A[j]) 
20            g[i]=max(g[i],g[j]+1);
21     } 
22     int ans=0;
23     for(int i=0;i1);  //      
24     cout<ans;
25     return 0;
26 }

 
 
最適化:
二分加速最適サブ問題を探す.時間的複雑度はO(nlogn)であり,データ範囲が小さいため加速効果は顕著ではない.
1、手書き二分はalgorithmの二分より速い.
2、memsetはfillより速い.
 

 1 #include
 2 #include
 3 using namespace std;
 4 
 5 const int maxn=105;
 6 const int INF=1<<30;
 7 
 8 int d[maxn],g[maxn],t[maxn];
 9 int A[maxn],n;
10 
11 //    
12 
13 inline int lower_bound(int l,int r,int k) {
14     int m;
15     while(l<r) {
16         int m=l+(r-l)/2;
17         if(k <= t[m]) r=m;
18         else l=m+1; 
19     }
20     return l; 
21 }
22 int main() {
23     ios::sync_with_stdio(false);
24     cin>>n;
25     for(int i=1;i<=n;i++) cin>>A[i];
26     memset(t,60,sizeof(t));
27     for(int i=1;i<=n;i++) {
28         d[i]=lower_bound(1,n+1,A[i]);
29         t[d[i]]=A[i];
30     }
31     
32     memset(t,60,sizeof(t));
33     for(int i=n;i;i--) {
34         g[i]=lower_bound(1,n+1,A[i]);
35         t[g[i]]=A[i];
36     }
37     
38     int ans=0;
39     for(int i=1;i<=n;i++) ans=max(ans,d[i]+g[i]-1);
40     cout<ans; 
41     return 0;
42 }