合唱队形  N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。 合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1, 2, …, K，他们的身高分别为T1, T2, …, TK，则他们的身高满足T1 < T2 < … < Ti , Ti > Ti+1 > … > TK (1 <= i <= K)。 你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。 Input 输入的第一行是一个整数N（2 <= N <= 100），表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti（130 <= Ti <= 230）是第i位同学的身高（厘米）。 Output 输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。 Sample Input 8186 186 150 200 160 130 197 220 Sample Output 4 ///////////////////////////////////////////////////////////////////////////////////////// 解题方法：Dp 设三个数组，其中一个用于保存身高，另外两个保存子状态。 up[n]表示身高一直按升序排列时，从第一个人到 第 n 个人合法排列的最大人数。down[n]表示混合的即可以从中间某个位置降序。假如输入数据为：43 4 1 2up[] = {1,2,1,2}, down[] = {1,1,3,3} 至少需要 n - max(up[],down[]), 即 4 - 3 = 1 测试数据：8186 186 150 200 160 130 197 22051 2 3 4 561 3 2 4 2 1结果：401/////////////////////////////////////////////////////////////////////////////////////// #include <stdio.h>#define MAX 110 int a[MAX],up[MAX],down[MAX];int getUp(int i){ int j,max; for(max=0,j=i-1; j>=0; j--)  if(a[i] > a[j] && up[j] > max)   max = up[j]; return max;}int getDown(int i){ int j,max; for(max=0,j=i-1; j>=0; j--){  if(a[i] < a[j]){   if(up[j] > max)    max = up[j];   if(down[j] > max)    max = down[j];  } } return max;}int main(){ int max,i,n; while(scanf("%d",&n)!=EOF){  scanf("%d",&a[0]);  for(max=up[0]=down[0]=1,i=1; i<n; i++){   scanf("%d",&a[i]);   up[i] = getUp(i)+1;   if(up[i] > max)    max = up[i];   down[i] = getDown(i)+1;   if(down[i] > max)    max = down[i];  }  printf("%d\n",n-max); } return 0;}

评论