题意:给一个队伍,要去掉最少的人,使得中间高,两边矮,
并且除了中间的那两个人有可能等高外,两两不能等高(右边的可以和左边的等高)。
动态规划,从左边正序找最长上升子序列,右边逆序找最长上升子序列;
#include <iostream> #include <algorithm> #include <cstring> #define N 1500 using namespace std; int main() { int n,i,j,dpl[N],dpr[N]; double a[N]; memset(dpl,0,sizeof(dpl)); memset(dpr,0,sizeof(dpr)); cin>>n; for(i=0; i<n; i++) cin>>a[i]; for(i=0; i<n; i++) { dpl[i]=1; for(j=0; j<i; j++) if(a[j]<a[i]) dpl[i]=max(dpl[i],dpl[j]+1); } for(i=n-1; i>=0; i--) { dpr[i]=1; for(j=n-1; j>i; j--) if(a[j]<a[i]) dpr[i]=max(dpr[i],dpr[j]+1); } int m=0; for(i=0; i<n; i++) { int v1=0,v2=0; for(j=0; j<i; j++) if(dpl[j]>v1) v1=dpl[j]; for(; j<n; j++) if(dpr[j]>v2) v2=dpr[j]; if(v1+v2>m) m=v1+v2; } cout<<n-m<<endl; return 0; }