题解 P1410 【子序列】

无解双八卦 · 2017-11-09 17:48:52 · 题解

emmm,感觉这题有问题啊。

问题出在题目：问能否将其划分为两个长度为N/2的严格递增子序列。

先贴一个能ac的代码：

#include<cstdio>
#include<cstring>
using namespace std;
int a[2005],a1[2005],a2[2005];
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int i,t=0,a1max=0,a2max=0;
        for(i=1;i<=n;i++)
        {a1[i]=-1;a2[i]=-1;}
        for(i=1;i<=n;i++)
        {scanf("%d",&a[i]);
        if(t==0)
        {
            if(a[i]>a1max){a1[i]=a[i];a1max=a1[i];}
            else if(a[i]>a2max)
            {a2[i]=a[i];a2max=a2[i];}
            else t=1;}}
        if(t==0)printf("Yes!\n");
        else printf("No!\n");
    }
    return 0;
}

很明显上面的代码只是判断是否能分成两个单增子序列而不考虑长度限制，然而能过。 这个还可以用数据水来解释，然而下面是一个（我认为的）正解代码，结果过不了：

#include<cstdio>
#include<cstring>
using namespace std;
int a[2005],a1[2005],a2[2005];
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int i,t=0,a1len=0,a2len=0,a1max=0,a2max=0,k1,k2=0,j,res=0;//res表示能从a1移到a2的数的个数
        for(i=1;i<=n;i++)
        {a1[i]=-1;a2[i]=-1;}
        a2[0]=-1;a2[n+1]=1000000001;
        for(i=1;i<=n;i++)
        {scanf("%d",&a[i]);
        if(t==0)
        {
            if(a[i]>a1max){a1[i]=a[i];a1max=a1[i];a1len++;}
            else if(a[i]>a2max)
            {a2[i]=a[i];a2max=a2[i];a2len++;
            k1=k2;k2=i;
            for(j=k1+1;j<k2;j++)
            if(a1[j]!=-1&&a1[j]>a2[k1]&&a1[j]<a2[k2])res++;}//每当输入一个a2,就搜索从上一个a2到这个a2可以移到a2的a1
            else t=1;}}
        for(j=k2+1;j<n+1;j++)
        if(a1[j]!=-1&&a1[j]>a2[k2]&&a1[j]<a2[n+1])res++;//最后再搜一遍
        if(t==0&&a1len>=n/2&&a2len+res>=n/2)printf("Yes!\n");
        else printf("No!\n");
    }
    return 0;
}

然而这个码只能过一个点，其它都会有应该输出Yes!而输出No!的情况 （我觉得）这个码应该没啥问题，所以题目有问题。

如果只是想过这道题，忽略掉题目里的子序列长度限制就好。