首页 > 代码库 > P1410 子序列

P1410 子序列

2024-10-16 20:36:02   205人阅读

题目描述

给定一个长度为N（N为偶数）的序列，问能否将其划分为两个长度为N/2的严格递增子序列，

输入输出格式

输入格式：

 

若干行，每行表示一组数据。对于每组数据，首先输入一个整数N，表示序列的长度。之后N个整数表示这个序列。

 

输出格式：

 

同输入行数。对于每组数据，如果存在一种划分，则输出“Yes!”，否则输出“No!“。

 

输入输出样例

输入样例#1：
6 3 1 4 5 8 76 3 2 1 6 5 4
输出样例#1：
Yes!No!

说明

【数据范围】

共三组数据，每组数据行数<=50，0 <= 输入的所有数 <= 10^9

第一组(30%)：N <= 20

第二组(30%)：N <= 100

第三组(40%)：N <= 2000

 

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #define INF (2139062143) 7 using namespace std; 8 const int MAXN=3001; 9 10 void read(int &n)11 {12     char c=‘+‘;int x=0;bool flag=0;13     while(c<‘0‘||c>‘9‘){c=getchar();if(c==‘-‘)flag=1;}14     while(c>=‘0‘&&c<=‘9‘)15     {x=x*10+c-48;c=getchar();}16     flag==1?n=-x:n=x;17 }18 int n;19 int a[MAXN];20 int dp[MAXN][MAXN];21 int main()22 {23     while(scanf("%d",&n)==1)24     {25         memset(a,0,sizeof(a));26         for(int i=1;i<=n;i++)27             read(a[i]);28         memset(dp,127,sizeof(dp));29         dp[1][1]=-1;30         for(int i=1;i<=n;i++)31         {32             for(int j=1;j<=i;j++)33             {34                 if(dp[i][j]!=INF)35                 {36                     if(a[i]<a[i+1])37                         if(dp[i+1][j+1]>dp[i][j])38                             dp[i+1][j+1]=dp[i][j];39                     if(dp[i][j]<a[i+1])40                         if(dp[i+1][i+1-j]>a[i])41                             dp[i+1][i+1-j]=a[i];42                 }43             }44         }45         if(dp[n][n/2]==INF)46             printf("No!\n");47         else 48             printf("Yes!\n");49     }50     return 0;51 }

 

P1410 子序列


联系
我们