洛谷P1410 子序列
2024-10-15 15:28:26
题目描述
给定一个长度为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
如果有两个数构成单调不升序列,那么这两个数必须被分在两个不同的严格上升序列里。如果有长度大于2的单调不升序列,两个严格上升序列放不下,那么就不可行。
/*by SilverN*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
const int mxn=;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int f[mxn];
int a[mxn];
int n;
int main(){
int i,j;
while(scanf("%d",&n)!=EOF){
for(i=;i<=n;i++){
f[i]=;
a[i]=read();
for(j=;j<i;j++)
if(a[j]>=a[i])f[i]=max(f[i],f[j]+);
}
bool flag=;
for(i=;i<=n;i++)
if(f[i]>){printf("No!\n");flag=;break;}
if(!flag)continue;
printf("Yes!\n");
} return ;
}
最新文章
- REDIS 字典数据结构
- MongoDB用户权限基本操作
- 有限状态机(Python)
- linux下卸载mysql
- session,cookie
- 1-2 ISO/OSI七层模型简介
- jQuery选择器之表单选择器Demo
- excel文档
- Python多线程(threading模块)
- Web中的性能优化
- Linux分配给该用户没有权限登陆
- aop为系统添加操作日志,注入或配置声明的方式来实现
- 后端传Long类型至前端js会出现精度丢失问题
- python实现ssh远程登录
- 博客六--Tensorflow卷积神经网络的自主搭建
- 【织梦dedecms安全设置】dedecms如何防止被黑?dedecms被黑了怎么办?
- HTML-JS 数组 内置对象
- Vue Create 创建一个新项目 命令行创建和视图创建
- asp.net 一般处理程序实现网站验证码
- 关于Telnet使用