题目描述
给定一个长度为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
Solution
这个题目看得我...
要用到正则难反则易的思想.与其作死想满足条件的状态,不如来思考一波什么情况下一定不会成立?
答案是可以得出的,当序列中存在一个 L>=3 的不递增子序列时,它就肯定不行.
证明:
由抽屉原理易知,如果有一个 长度为 3 的不递增子序列,那么我们划分的序列至少一个序列要分到 2 个不递增的序列. 此时我们所分的序列即不满足条件.
然后就可以简单地进行DP了... 可以 O(n^2) 求解
代码
#include<bits/stdc++.h>
using namespace std;
int c[2008],f[2008],n;
int main()
{
while(scanf("%d",&n)==1)
{
memset(f,0,sizeof(f));
int ans=0;
for(int i=1;i<=n;i++) scanf("%d",&c[i]);
for(int i=1;i<=n;i++)
{
f[i]=1;
for(int j=1;j<i;j++)
if(c[i]<=c[j])
f[i]=max(f[i],f[j]+1);
ans=max(ans,f[i]);
}
if(ans<=2) cout<<"Yes!"<<endl;
else cout<<"No!"<<endl;
}
}