子序列(省略已知值法与挪位得解法)


		Problem 1 子序列(subsequence.pas/c/cpp)
【题目描述】
给定一个长度为N（N为偶数）的序列，问能否将其划分为两个长度为N/2的严格递增子序列，
 
【输入格式】
若干行，每行表示一组数据。对于每组数据，首先输入一个整数N，表示序列的长度。之后N个整数表示这个序列。
 
【输出格式】
同输入行数。对于每组数据，如果存在一种划分，则输出“Yes!”，否则输出“No!“。
 
【样例输入】
6 3 1 4 5 8 7
6 3 2 1 6 5 4
【样例输出】
Yes!
No!
【数据范围】
共三组数据，每组数据行数<=50，0 <= 输入的所有数 <= 10^9
第一组(30%)：N <= 20
第二组(30%)：N <= 100
第三组(40%)：N <= 2000
 
一般青年Dp方案：F[i][j][k][l] 表示前i+j位分为一个长度为i以j结尾，一个长度为k以l结尾的序列 是否可行(0,1)
省略已知值：观察发现j和l中至少有一个为a[i+j]
故可省略其中一位
n=2000必跪
文艺青年Dp方案：
挪位得解：把f[i][j][k]中的k挪出来 
原因：显然i和j不变时，我们希望k越小越好
所以记录min(k)，并记录无解情况
O(n^2)
 
[cpp] 
#include<cstdio>  
#include<iostream>  
#include<algorithm>  
#include<functional>  
#include<cstdlib>  
#include<cstring>  
#include<cmath>  
using namespace std;  
#define MAXN (2000+10)  
#define INF (2139062143)  
int n,a[MAXN],f[MAXN][MAXN];  
int main()  
{  
    freopen("subsequence.in","r",stdin);  
    freopen("subsequence.out","w",stdout);  
    while (scanf("%d",&n)!=EOF)  
    {  
        memset(f,127,sizeof(f));  
        for (int i=1;i<=n;i++) scanf("%d",&a[i]);  
        f[1][1]=-1;  
        for (int i=1;i<n;i++)  
        {  
            for (int j=1;j<=i;j++)  
            {  
                if (f[i][j]!=INF)  
                {  
                    if (a[i]<a[i+1]) f[i+1][j+1]=min(f[i+1][j+1],f[i][j]);  
                    if (f[i][j]<a[i+1])  
                        f[i+1][i-j+1]=min(f[i+1][i-j+1],a[i]);  
                }  
            }     
        }  
        /* 
        for (int i=0;i<=n;i++) 
        { 
            for (int j=0;j<=n;j++) 
                printf("%d ",f[i][j]); 
            printf("\n"); 
        } 
        */  
        if (f[n][n>>1]!=INF) printf("Yes!\n");  
        else printf("No!\n");         
    }     
    return 0;  
}

补充：软件开发 , C++ ,