请选择 进入手机版 | 继续访问电脑版

hdu1087 最大加和上升子序列

[复制链接]
孤单 发表于 2020-12-31 19:00:43 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
首先,标题的“最大加和上升子序列”是我自己起的名字。
实际上这题跟最长上升子序列(LIS)很像。
最长上升子序列就是,选取一个子序列(子序列是可以不一连的),让他能保持单调递增,且求出这个单调递增子序列的最长的是长度是多少。
就是记dp是以a末端的LIS长度。
我们首先要包管在盘算的序列他是递增的。而且因为dp是停止到a的,我们就思量,前面的序列(1 ~ j, j  a[j],那么dp = dp[j] +1。则我们所要求的就是:dp = max(dp, dp[j] +1),最终的LIS就是max(dp)
可团结这个视频来看
  这个题就非常相似,实际上就是一种变形
我们照旧设dp施以a末端的最大加和。
根本同理,就是我们需要判断,前面的那些满意a > a[j] 的dp[j] + a与当前求出来的dp哪个更大。
对dp[j] + a 的表明就是,在满意谁人前提下,前面已求出来的加上现在这个数,与当前知道的最大的dp做比力,取大的,就是我们要的答案。
[code]#include #include #include #include #include #define ll long longusing namespace std;ll dp[1000 + 10]; //1 tiao 0 bu_tiaoint n;int a[1000 + 10];void debug(){        for(int i = 1; i  a;                }                ll ans = -999999;                for(int i = 1; i
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

发布主题

专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )