[ CodeVS冲杯之路 ] P1044
2024-10-21 15:27:22
不充钱,你怎么AC?
题目:http://codevs.cn/problem/1044/
机房连续断网,搞得现在才能上博客……
很经典的DP题,把问题转换一下就是分别求最不降序列和最长上升序列
f[i][j] 表示可以选择多少个,第一问
目标状态是 max(f[i])
第二问同理,仅仅是把条件的符号换了一下
目标状态也是 max(f[i])
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define oo 2147483647
#define N 21
using namespace std; int a[N],f[N],n,ans,last[N];
int main()
{
int i=,j;
while (scanf("%d",&a[++i])!=EOF);
n=i-;
a[]=oo;
for (i=;i<=n;i++)
{
for (j=;j<i;j++)
{
if (a[j]>=a[i])
{
if (f[i]<f[j]+)
{
f[i]=f[j]+;
ans=max(ans,f[i]);
}
}
}
}
printf("%d\n",ans);
a[]=;
ans=;
for (i=;i<=n;i++)
{
f[i]=;
for (j=;j<i;j++)
{
if (a[j]<a[i])
{
if (f[i]<f[j]+)
{
f[i]=f[j]+;
ans=max(ans,f[i]);
}
}
}
}
printf("%d\n",ans);
return ;
}
最新文章
- 转(zip文件格式说明)
- python 将数据随机分为训练集和测试集
- Month Calendar
- Light OJ 1011 - Marriage Ceremonies(状压DP)
- php在.php文件中设置php.ini,仅对当前文件有效
- VHDL testbench 例子,包含向文件中写数据
- PRML 第三章 - 线性回归
- XML和JSON两种数据交换格式的比较
- yaf框架加载全局公共函数
- WebDriver Selenium eclipse环境搭建
- 关于申请GMS认证来使用谷歌的一些服务应用及闭源API
- 20190317 A
- nginx 日志 cron任务切割日志
- windows 端口被占用,并杀死进程的方法
- LeetCode(49): 字母异位词分组
- LeetCode题库13. 罗马数字转整数(c++实现)
- Clustered Shading架构实现步骤
- 使用安全rm
- Java数据结构和算法(一)树
- sprint会议1