codevs——T1576 最长严格上升子序列
2024-08-31 08:14:38
题目描述 Description
给一个数组a1, a2 ... an,找到最长的上升降子序列ab1<ab2< .. <abk,其中b1<b2<..bk。
输出长度即可。
输入描述 Input Description
第一行,一个整数N。
第二行 ,N个整数(N < = 5000)
输出描述 Output Description
输出K的极大值,即最长不下降子序列的长度
样例输入 Sample Input
5
9 3 6 2 7
样例输出 Sample Output
3
数据范围及提示 Data Size & Hint
【样例解释】
最长不下降子序列为3,6,7
序列DP
#include <algorithm>
#include <cstdio> using namespace std; int n,ans;
int a[],f[]; int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
for(int i=;i<=n;i++)
for(int j=;j<i;j++)
if(a[j]<a[i]) f[i]=max(f[j]+,f[i]);
for(int i=;i<=n;i++)
ans=max(ans,f[i]);
printf("%d",ans+);
return ;
}
最新文章
- B树
- 《java编程思想》读书笔记(二)第五章(2)
- JQuery源码解析-- 对象的创建
- UESTC 288 青蛙的约会 扩展GCD
- php substr中文乱码最有效到解决办法 转:http://blog.sina.com.cn/s/blog_49b531af0100esah.html
- 数学 Codeforces Round #291 (Div. 2) B. Han Solo and Lazer Gun
- 兼容主流浏览器的CSS透明代码
- centos6.7下编译安装lamp环境
- JS操作CSS样式
- Android开发之ViewPager
- 检测到有潜在危险的Request.Form值
- Libevent源码分析(一):最小堆
- css-选择器-优先级
- iOS_SN_深浅拷贝( 百度的)_转载
- vue cookie
- Nginx三部曲(1)基础
- Manjaro下带供电的USB Hub提示error -71
- bouncing-balls
- MyCat(一) - 初体验
- entity framework 时间操作
热门文章
- C++一些知识难点
- 如何正确产看API
- 移动端 fixed 固定按钮在屏幕下方,然后按钮被键盘顶上来...顶上来了有没有~
- vuejs开发H5页面总结
- 登录linux,输入ls显示anaconda-ks.cfg cobbler.ks ....., 原因在于root@ ~ / 区别
- javascript的基础知识及面向对象和原型属性
- AVD的Hardware选项
- date 格式化
- java学习笔记4——返回值
- ZBrush中如何将一个模型应用在不同的图层