- 时空限制1s / 128MB
题目描述
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包括一行，这一行只包含一个整数，就是最少需要几位同学出列。
输入输出样例
说明
对于50％的数据，保证有n<=20；
对于全部的数据，保证有n<=100。
-----------------------------------------------------------------------------------------------------------------
最长上升子序列+最长下降子序列
写这道题之前，你要知道如何求一个序列的最长上升/下降子序列
可以看我的一篇随笔：http://www.cnblogs.com/lpl-bys/p/7701945.html
用dpu[i][j]表示从第i个数到第j个数构成的序列里的最长上升子序列
dpd[i][j]表示从第i个数到第j个数构成的序列里的最长下降子序列
需要注意的是dpu[i][j]和dpd[i][j]所表示的最长子序列都必须从第i个数开始的，这就不便于后面把这两个序列合起来
所以我们需要再开另外两个二维数组:
up[i][j]表示从第i个数到第j个数构成的序列里的最长上升子序列
dow[i][j]表示从第i个数到第j个数构成的序列里的最长下降子序列
可以看到，这两个数组才是真正的表示从第i个数到第j个数构成的序列里的最长上升/下降子序列的长度（即不必从第i个数开始）
后面就容易多了
具体看代码体会吧：
1 #include<stdio.h> 2 #include<string.h> 3 #include<iostream> 4 #define maxn 233 5 using namespace std; 6 int read(); 7 int n,a[maxn],dpu[maxn][maxn],dpd[maxn][maxn],ans,up[maxn][maxn],dow[maxn][maxn]; 8 int main(){ 9 n=read(); 10 for(int i=1;i<=n;i++) a[i]=read(); 11 for(int i=1;i<=n;i++) 12 for(int j=i;j>0;j--){ 13 for(int k=j;k<=i;k++){ 14 if(j==k) dpu[k][i]=dpd[k][i]=1;//不同于不严格的，因为是求严格上升/下降序列的，所以需要这一步初始化 15 if(a[j]<a[k]&&dpu[k][i]+1>dpu[j][i]) dpu[j][i]=dpu[k][i]+1; 16 if(a[j]>a[k]&&dpd[k][i]+1>dpd[j][i]) dpd[j][i]=dpd[k][i]+1; 17 up[j][i]=max(up[j][i],dpu[k][i]); 18 dow[j][i]=max(dow[j][i],dpd[k][i]); 19 } 20 up[j][i]=max(up[j][i],dpu[j][i]); 21 dow[j][i]=max(dow[j][i],dpd[j][i]); 22 } 23 ans=0; 24 for(int i=0;i<=n;i++) 25 if(up[1][i]+dow[i+1][n]>ans) ans=up[1][i]+dow[i+1][n]; 26 printf("%d",n-ans); 27 return 0; 28 } 29 int read(){ 30 int ans=0,f=1;char c=getchar(); 31 while('0'>c||c>'9'){if(c=='-')f=-1;c=getchar();} 32 while('0'<=c&&c<='9')ans=ans*10+c-48,c=getchar();return ans*f; 33 }