I题解--“歌尔创客杯”第二届哈尔滨理工大学（荣成）程序设计竞赛

I 完美主义者
dp,最长子序列的衍生。
可参考经典题拦截导弹，那个是最长递增子序列。

代码：

#include <bits/stdc++.h>
using namespace std;
int inc1[200],inc2[200],a[200];
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        int ans=0,i,j;
        for(i = 0; i < n; i++)scanf("%d",&a[i]);
        //inc1[i]是存储以i为最高点时左边的递增子序列长度
        inc1[0]=1;
        for(i = 1; i < n; i++){
            inc1[i] = 1;
            for(j = 0; j < i; j++)
                if(a[i] > a[j] && inc1[j] + 1 > inc1[i])
                    inc1[i] = inc1[j]+1;
        }
        //inc2[i]是存储以i为最高点时左边的递减子序列长度
        inc2[n - 1] = 1;
        for(i = n - 2; i >= 0; i--){
            inc2[i] = 1;
            for(j = n - 1; j > i; j--)
                if(a[j] < a[i] && inc2[j] + 1 > inc2[i])
                    inc2[i] = inc2[j] + 1;
        }
        for(i = 0; i<=n; i++)
            if(inc1[i] + inc2[i]-1 > ans) 
                ans = inc1[i] + inc2[i] - 1;//总长度为左右长度相加-1，因为多算了自己一次。
        printf("%d\n",n-ans);
    }
    return 0;
}