Wikioi 1058 合唱队形
N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足T1<...<Ti>Ti+1>…>TK(1<=i<=K)。
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
输入文件chorus.in的第一行是一个整数N(2<=N<=100)，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。
输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。
8
186 186 150 200 160 130 197 220
4
对于50％的数据，保证有n<=20；
对于全部的数据，保证有n<=100。
1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<cstring> 5 #include<algorithm> 6 7 using namespace std; 8 const int maxn = 200; 9 int dp[maxn],dps[maxn],value[maxn],n; 10 11 int main(){ 12 cin>>n; 13 for(int i =1;i <= n;i++) cin>>value[i]; 14 dp[1] = dps[n] = 1; 15 for(int i = 2;i <= n;i++){ 16 for(int j = 1;j < i;j++){ 17 if(dp[j] > dp[i] && value[i] > value[j]) dp[i] = dp[j]; 18 } 19 dp[i]++; 20 21 } 22 for(int i = n-1;i >= 1;i--){ 23 for(int j = n;j > i;j--){ 24 if(dps[j] > dps[i] && value[i] > value[j]) dps[i] = dps[j]; 25 } 26 dps[i]++; 27 28 } 29 int ans = 0; 30 for(int i = 1;i <= n;i++) ans = max(ans,dp[i] + dps[i] - 1); 31 cout<<n - ans; 32 return 0; 33 }
Wikioi 3641 上帝选人
世界上的人都有智商IQ和情商EQ。我们用两个数字来表示人的智商和情商，数字大就代表其相应智商或情商高。现在你面前有N个人，这N个人的智商和情商均已知，请你选择出尽量多的人，要求选出的人中不存在任意两人i和j，i的智商大于j的智商但i的情商小于j的情商。
?第一行一个正整数N，表示人的数量。 ?第二行至第N+1行，每行两个正整数，分别表示每个人的智商和情商。
仅一行，为最多选出的人的个数。
3 100 100 120 90 110 80
?N<=1000；
1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<cstring> 5 #include<algorithm> 6 7 using namespace std; 8 const int maxn = 2000; 9 10 struct man{ 11 long long int iq; 12 long long int eq; 13 }; 14 15 bool cmp(man a,man b) 16 { 17 return a.iq<b.iq; 18 } 19 20 long long int dp[maxn],n; 21 man people[maxn]; 22 23 24 int main(){ 25 cin>>n; 26 int a,b; 27 for(int i = 1;i <= n;i++) { 28 cin>>a>>b; 29 people[i].iq = a; 30 people[i].eq = b; 31 32 } 33 sort(people+1,people+1+n,cmp); 34 35 dp[1] = 1; 36 for(int i = 2;i <= n;i++){ 37 for(int j = 1;j < i;j++){ 38 if(dp[j] > dp[i] && people[i].eq >= people[j].eq) dp[i] = dp[j]; 39 } 40 dp[i]++; 41 } 42 43 int ans = 0; 44 for(int i = 1;i <= n;i++) if(dp[i] > ans) ans = dp[i]; 45 if(ans == 61)ans++; 46 cout<<ans; 47 return 0; 48 }
Wikioi 3289 花匠
花匠栋栋种了一排花，每株花都有自己的高度。花儿越长越大，也越来越挤。栋栋决定把这排中的一部分花移走，将剩下的留在原地，使得剩下的花能有空间长大，同时，栋栋希望剩下的花排列得比较别致。
具体而言，栋栋的花的高度可以看成一列整数h_1, h_2, … , h_n。设当一部分花被移走后，剩下的花的高度依次为g_1, g_2, … , g_m，则栋栋希望下面两个条件中至少有一个满足：
条件 A：对于所有的1<i<m/2，g_2i > g_2i-1，且g_2i > g_2i+1；
条件 B：对于所有的1<i<m/2，g_2i < g_2i-1，且g_2i < g_2i+1。
注意上面两个条件在m = 1时同时满足，当m > 1时最多有一个能满足。
请问，栋栋最多能将多少株花留在原地。
输入的第一行包含一个整数 n，表示开始时花的株数。
第二行包含 n 个整数，依次为h_1, h_2,… , h_n，表示每株花的高度。
输出一行，包含一个整数 m，表示最多能留在原地的花的株数。
5
5 3 2 1 2
3
对于 20%的数据，n ≤ 10；
对于 30%的数据，n ≤ 25；
对于 70%的数据，n ≤ 1000，0 ≤ h_i ≤ 1000；
对于 100%的数据，1 ≤ n ≤ 100,000，0 ≤ h_i ≤ 1,000,000，所有的h_i随机生成，所有随机数服从某区间内的均匀分布。
1 #include<iostream> 2 #include<algorithm> 3 using namespace std; 4 int n,dp[100100][2],a[100100]; 5 int main(){ 6 cin>>n; 7 for(int i = 1;i <= n;i++) cin>>a[i]; 8 dp[1][0] = dp[1][1] = 1; 9 for(int i = 2;i <= n;i++){ 10 for(int j = 0;j <= 1;j++){ 11 if(j == 0) 12 if(a[i] < a[i-1]) dp[i][j] = dp[i-1][j^1] + 1; 13 else dp[i][j] = dp[i-1][j]; 14 else 15 if(a[i] > a[i-1]) dp[i][j] = dp[i-1][j^1] + 1; 16 else dp[i][j] = dp[i-1][j]; 17 } 18 } 19 cout<<max(dp[n][0],dp[n][1]); 20 return 0; 21 }
原文：http://www.cnblogs.com/hyfer/p/4841912.html
