给定一个长度为N(N为偶数)的序列,问能否将其划分为两个长度为N/2的严格递增子序列,
输入格式:
若干行,每行表示一组数据。对于每组数据,首先输入一个整数N,表示序列的长度。之后N个整数表示这个序列。
输出格式:
同输入行数。对于每组数据,如果存在一种划分,则输出“Yes!”,否则输出“No!“。
输入样例#1:
6 3 1 4 5 8 7
6 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 }