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

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位分为一个长度为ij结尾,一个长度为kl结尾的序列
是否可行(0,1)

省略已知值:观察发现jl中至少有一个为a[i+j]

故可省略其中一位

n=2000必跪

文艺青年Dp方案:

挪位得解:把f[i][j][k]中的k挪出来 

原因:显然i和j不变时,我们希望k越小越好

所以记录min(k),并记录无解情况

O(n^2)

#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;
}