原题链接地址:http://acm.hdu.edu.cn/diy/contest_showproblem.php?pid=1003&cid=10908&hide=0
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int arr[120],dp1[120],dp2[120]; int main() { int n; while(scanf("%d",&n)!=EOF) { if(n<0) break; for(int i=1;i<=n;i++) scanf("%d",&arr[i]); dp1[1]=1; int ans; for(int i=2;i<=n;i++) { ans=0; for(int j=1;j<i;j++) if(arr[i]>arr[j]&&dp1[j]>ans) ans=dp1[j]; dp1[i]=ans+1; /*ans=1; for(int j=1;j<i;j++) if(arr[i]<arr[j]&&dp2[j]>ans) ans=dp2[j]; dp2[i]=ans;*/ } dp2[n]=1; for(int i=n-1;i>=1;i--) { ans=0; for(int j=n;j>i;j--) if(arr[i]>arr[j]&&dp2[j]>ans) ans=dp2[j]; dp2[i]=ans+1; } /*for(int i=1;i<=n;i++) printf("%d ",dp1[i]); printf("\n"); for(int i=1;i<=n;i++) printf("%d ",dp1[i]); printf("\n\n");*/ ans=100; for(int i=1;i<=n;i++) if(n-(dp1[i]+dp2[i]-1)<ans) ans=n-(dp1[i]+dp2[i]-1); printf("%d\n",ans); } system("pasue"); return 0; }