信息学奥赛一本通 1285:最大上升子序列和(evd)
发布日期:2022-01-30 02:41:35
浏览次数:12
分类:技术文章
本文共 726 字,大约阅读时间需要 2 分钟。
【题目描述】
一个数的序列bi,当b1<b2<…<bS的时候,我们称这个序列是上升的。对于给定的一个序列(a1,a2,…,aN),我们可以得到一些上升的子序列(ai1,ai2,…,aiK),这里1≤i1<i2<…<iK≤N。比如,对于序列(1,7,3,5,9,4,8),有它的一些上升子序列,如(1,7),(3,4,8)等等。这些子序列中和最大为18,为子序列(1,3,5,9)的和。你的任务,就是对于给定的序列,求出最大上升子序列和。注意,最长的上升子序列的和不一定是最大的,比如序列(100,1,2,3)的最大上升子序列和为100,而最长上升子序列为(1,2,3)。
【输入】
输入的第一行是序列的长度N(1≤N≤1000)。第二行给出序列中的N个整数,这些整数的取值范围都在0到10000(可能重复)。【输出】
最大上升子序列和。【输入样例】
7 1 7 3 5 9 4 8 【输出样例】 18 【心得】通LIS,用f[i]表示当前序列的和,找上一个阶段最大的那个,更新现在的就够了! 【AC代码】#include#include #include #include using namespace std;const int N=1005;int n,a[N],f[N],ma;int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; f[n]=a[n]; for(int i=n-1;i>=1;i--) { ma=0; for(int j=i+1;j<=n;j++) if(a[i]
转载地址:https://blog.csdn.net/everwide1982/article/details/109745376 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
很好
[***.229.124.182]2024年04月05日 20时44分11秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
海量数据处理
2019-04-27
PHP防止注入攻击
2019-04-27
多路IO复用模型 select epoll 等
2019-04-27
Linux Epoll介绍和程序实例
2019-04-27
output_buffering详细介绍
2019-04-27
php缓冲 output_buffering和ob_start
2019-04-27
php error_reporting 详解
2019-04-27
剖析PHP中的输出缓冲
2019-04-27
HTTP响应头不缓存
2019-04-27
PHP安装扩展mcrypt以及相关依赖项 【PHP安装PECL扩展的方法】
2019-04-27
Javascript到PHP加密通讯的简单实现
2019-04-27
德国SNS交友/视频网站Poppen.de的技术架构分享
2019-04-27
UNIX环境编程
2019-04-27
一笔画问题【数据结构-图论】
2019-04-27
红黑树
2019-04-27
安装多个gcc
2019-04-27
Linux0.01内核根目录Makefile注释
2019-04-27
【CSDN2012年度博客之星】需要您的一票,感谢大家的支持
2019-04-27
PHP对于浮点型的数据需要用不同的方法去解决
2019-04-27
Tokyo Cabinet 安装
2019-04-27