题解 P1410 【子序列】

如楼下所说，下面两个题解是有反例的，如输入数据为 6 1 2 3 4 5 1 时就不行了。

然而数据弱呀╮(╯▽╰)╭

那么这个题解的思路显然不是我自己的

http://blog.csdn.net/nike0good/article/details/8605219

【蒟蒻表示花了很久看懂大神的题解……】

在前i位中找长j位的以第i位结尾的上升子序列，并且剩下的也是上升子序列，那么f[i][j]表示剩下的（即前i位中长i-j位的不以第i位结尾的）上升子序列的最后一位的最小值。

然后转移：

如果a[i]<a[i+1]，那么f[i+1][j+1]=min(f[i+1][j+1],f[i][j])，相当于可以直接把f[i][j]扩展到第i+1位。

如果f[i][j]<a[i+1]，那么f[i+1][i-j+1]=min(f[i+1][i-j+1],a[i])，相当于第i+1继承前i位中i-j位长的上升子序列。

#include <iostream>
#include <cstdio>
#include <cstring>
#define INF (2139062143)
using namespace std;
void read(int& x){
    x=0;
    int y=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') y=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    x=x*y;
}
int n,a[2001],f[2001][2001];
int main(){
    int i,j;
    while (~scanf("%d",&n)){
        memset(f,127,sizeof(f)); 
        for (i=1;i<=n;++i){
            read(a[i]);
        }
        f[1][1]=-1;
        for (i=1;i<=n;++i){
            for (j=1;j<=i;++j){
                if (f[i][j]!=INF){
                    if (a[i]<a[i+1])
                        if (f[i+1][j+1]>f[i][j]) f[i+1][j+1]=f[i][j];
                    if (f[i][j]<a[i+1]) 
                        if (f[i+1][i+1-j]>a[i]) f[i+1][i+1-j]=a[i];
                }
            }
        }
        if (f[n][n/2]==INF) printf("No!\n");
        else printf("Yes!\n");
    }
    return 0;
}