[NOIP 提高组] 合唱队形 - 洛谷
思路：最少出列，即挑出最多，即找最长递增子序列和最长递减子序列
设dp1[i]为以h[i]结尾的最长递增子序列
dp2[i]为以h[i]开头的最长递减子序列
结果为n-(dp1[i]+dp2[i]-1)的最小值
注意max,min；
注意1~n还是0~n-1;
注意结果要-1(h[i]算2次)
如果思路对，举简单例子调试
#include<iostream>#include<algorithm>using namespace std;int n;int h[101];int dp1[101];//存放以h[i]为结尾的最长递增子序列的长度int dp2[101];//存放以h[i]为起点的最长递减子序列的长度 int main(){cin>>n;for(int i=0;i<100;i++){dp1[i]=1;dp2[i]=1;}for(int i=1;i<=n;i++){cin>>h[i];}dp1[0]=0;dp1[1]=1;for (int i = 2; i <= n; i++){for (int j = 1; j <= i - 1; j++){if (h[j] < h[i])dp1[i] = max(dp1[i], dp1[j] + 1);}}dp2[n - 1] = 1;for (int i = n - 2; i >= 0; i--) {for (int j = i + 1; j <= n - 1; j++){if (h[j] < h[i])dp2[i] = max(dp2[i], dp2[j] + 1);}}int res = 0;for (int i = 1; i <= n; i++){res = max(res, dp1[i] + dp2[i])-1;}cout << n-res;}
