P1410 子序列 (动态规划)
2024-09-30 06:57:08
题目描述
给定一个长度为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;
}
}
最新文章
- android必须要进行为不同分辨率设备切图
- Yii框架,在页面输出执行sql语句,方便调试
- 第三章DOM
- JS调用客户端EXE
- SVN上传代码时代码失败
- 【BZOJ3130】费用流(最大流,二分)
- 16个必须熟悉的linux服务器监控命令
- python错误和异常
- java List<;Map<;String,Object>;遍历的方法
- poj2393 Yogurt factory(贪心,思考)
- windows7,python3使用time.strftime()函数报ValueError: embedded null byte
- Python3学习之路~2.9 字符编码与转码
- C语言:逻辑推理
- Codeforces Round #390 (Div. 2) A. Lesha and array splitting
- 在wamp下增加多版本的PHP(PHP5.3,PHP5.4,PHP5.5)支持
- 020:Buffer Pool 、压缩页、CheckPoint、Double Write、Change Buffer
- python图片黑白化
- 【Python】python中的__dict__,__getattr__,__setattr__
- 5-1、easyUI-菜单与按钮(上节问题与解决)
- enumerate()函数