频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
子序列(省略已知值法与挪位得解法)
2013-02-25 08:13:42           
收藏   我要投稿
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;  

}  

 

点击复制链接 与好友分享!回本站首页
相关TAG标签 解法 序列
上一篇:HAC-UM无线数传模块使用总结
下一篇:swap(a,b)值交换的4种方法
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站