dp(4):1 6 4 9 : 【 入 门 】 前 缀 最 大 值

1 6 4 9 : 【 入 门 】 前 缀 最 大 值链接1649 - 前缀最大值-东方博宜OJ题目1 6 4 9 : 【 入 门 】 前 缀 最 大 值题目描述求一个数列的所有前缀最大值之和。即给出长度为 nn 的数列 aiai​求出对于所有 1≤i≤n1≤i≤nmax(a1,a2,...,ai)max(a1​,a2​,...,ai​) 的和。比如有数列666666 304304 692692 188188 596596前缀最大值为666666 666666 692692 692692 692692和为 34083408。对于每个位置的前缀最大值解释如下对于第 11 个数 666666 只有一个数一定最大对于第 22 个数求出前两个数的最大数还是 666666 对于第 33 个数求出前 33 个数的最大数是 692…692… 其余位置依次类推最后求前缀最大值得和。由于读入较大数列由随机种子生成。其中 a[1]xa[1]xa[i](379×a[i−1]131)mod997a[i](379×a[i−1]131)mod997。modmod 代表求余数输入一行两个正整数 nn, xx 分别表示数列的长度和随机种子。(n≤100000n≤100000x997x997)输出一行一个正整数表示该数列的前缀最大值之和。样例输入复制5 666输出复制3408说明样例解释数列为 666,304,692,188,596666,304,692,188,596前缀最大值为666,666,692,692,692666,666,692,692,692和为 34083408。来源动态规划标签动态规划题目参数时间限制1 秒内存限制16 MB提交次数9179通过人数6376金币数量1 枚难度入门思路a数组存放元素dp数组存储状态存储每个数的前缀最大值dp[1]a[1]dp[2]max(a[1],a[2])dp[3]max(a[1],a[2],a[3])max(dp[2],a[3])dp[4]max(a[1],a[2],a[3],a[4])max(dp[3],a[4])归纳得知动态转移方程如下dp[i]max(dp[i-1],a[i])dp[1]a[1](边界)前i个数的最大数max(前i-1个数的最大数a[i])解题步骤1、划分阶段2、确定状态和状态变量3、确定决策和状态转移方程4、寻找边界条件代码#includeiostream #includecmath using namespace std; /* 解题步骤 1、 划分阶段 2、 确定状态和状态变量 3、 确定决策和状态转移方程 4、 寻找边界条件 归纳得知动态转移方程如下 dp[i]max(dp[i-1],a[i]) dp[1]a[1] (边界) 前 i个 数 的 最 大 数 max ( 前 i-1个数的最大数a[i]) */ int n,a[100100],dp[100100],x; int main(){ cinnx; a[1]x; //边界条件 dp[1]a[1]; sdp[i];//求和 for(int i2;in;i){ a[i](379*a[i-1]131)%997; //计算出前i个数的最大值 dp[i]max(dp[i-1],a[i]); ssdp[i]; } coutsendl; return 0; }结尾【如果这篇文章对您有所帮助期待您的打赏这会是我继续创作下去的动力 】