P1410 子序列
2024-10-01 06:52:50
题目描述
给定一个长度为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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define INF (2139062143)
using namespace std;
const int MAXN=; void read(int &n)
{
char c='+';int x=;bool flag=;
while(c<''||c>''){c=getchar();if(c=='-')flag=;}
while(c>=''&&c<='')
{x=x*+c-;c=getchar();}
flag==?n=-x:n=x;
}
int n;
int a[MAXN];
int dp[MAXN][MAXN];
int main()
{
while(scanf("%d",&n)==)
{
memset(a,,sizeof(a));
for(int i=;i<=n;i++)
read(a[i]);
memset(dp,,sizeof(dp));
dp[][]=-;
for(int i=;i<=n;i++)
{
for(int j=;j<=i;j++)
{
if(dp[i][j]!=INF)
{
if(a[i]<a[i+])
if(dp[i+][j+]>dp[i][j])
dp[i+][j+]=dp[i][j];
if(dp[i][j]<a[i+])
if(dp[i+][i+-j]>a[i])
dp[i+][i+-j]=a[i];
}
}
}
if(dp[n][n/]==INF)
printf("No!\n");
else
printf("Yes!\n");
}
return ;
}
最新文章
- WCF : 修复 Security settings for this service require Windows Authentication but it is not enabled for the IIS application that hosts this service 问题
- 安装cocoapods遇到两大坑-Ruby版本升级和Podfile的配置
- <;c:if>;标签的使用-流程控制标签
- equals函数
- mysql 5.6.20的安装、配置服务、设置编码格式
- ListView 行高设置不起作用
- Hyper-v 虚拟机安装win7
- Android开发艺术探索——新的征程,程序人生路漫漫!
- js文档节点关系
- spring-cloud-config——Quick Start
- linux POSIX 信号量介绍
- Oracle创建database link(dblink)和同义词(synonym)
- IO、NIO、AIO
- apache -- 端口被占用
- 写写Django中DRF框架概述以及序列化器对象serializer的构造方法以及使用
- ThinkPHP出现General error: 2006 MySQL server has gone away的解决方法
- SpringBoot25 gradle安装、利用gradle创建SrpingBoot项目
- 拉登是我罩的队_第三周_需求改进&;原型设计
- 响应式布局--设置rem自适应
- javascript给输入框赋值的一个误区