Problem Address：http://poj.org/problem?id=1836
还是一道DP题，弄了半个晚上没弄好，没办法，去睡觉。
早上想早点起，结果错过了闹钟。
看了一下，居然就把错误找出来了。
提交，AC。好自在~
冲碗红烧牛肉泡面吃一下，难为了昨晚睡觉的时候肚子还咕咕叫，估计是费脑力了。
思路是对每一个数向两边求递减和递增的最长序列。不过要注意存在中间相等的情况。
以下贴代码：
#include <iostream>using namespace std;double s[1005],dp[1005];struct end{ int ct; int m;};end ddp(int len){ int i,j,ct; ct = 0; for (i=0; i<len; i++) { for (j=0; j<ct; j++) { if (dp[i]>=dp[j]) { dp[j] = dp[i]; break; } } if (j==ct) { dp[j] = dp[i]; ct++; } } end e; e.ct = ct; e.m = dp[0]; return e;}int main(){ int n,total,i,j,k,max; end L,R; scanf("%d", &n); for (i=0; i<n; i++) { scanf("%lf", &s[i]); } max = 0; for (k=0; k<n; k++) { for (i=k-1,j=0; i>=0; i--) { if (s[i]<=s[k]) dp[j++]=s[i]; } if (j!=0) { L = ddp(j); } else { L.ct = 0; L.m = -1; } for (i=k+1,j=0; i<n; i++) { if (s[i]<=s[k]) dp[j++]=s[i]; } if (j!=0) { R = ddp(j); } else { R.ct = 0; R.m = -1; } if (L.m==s[k] && R.m==s[k]) total = L.ct+R.ct; else total = L.ct+R.ct+1; if (total>max) max = total; } printf("%d/n", n-max); return 0;}
