hdu1024 Max Sum Plus Plus--DP
发布日期:2021-10-03 20:32:00
浏览次数:4
分类:技术文章
本文共 2143 字,大约阅读时间需要 7 分钟。
原题链接:
一:原题内容
Problem Description
Now I think you have got an AC in Ignatius.L's "Max Sum" problem. To be a brave ACMer, we always challenge ourselves to more difficult problems. Now you are faced with a more difficult problem. Given a consecutive number sequence S 1, S 2, S 3, S 4 ... S x, ... S n (1 ≤ x ≤ n ≤ 1,000,000, -32768 ≤ S x ≤ 32767). We define a function sum(i, j) = S i + ... + S j (1 ≤ i ≤ j ≤ n). Now given an integer m (m > 0), your task is to find m pairs of i and j which make sum(i 1, j 1) + sum(i 2, j 2) + sum(i 3, j 3) + ... + sum(i m, j m) maximal (i x ≤ i y ≤ j x or i x ≤ j y ≤ j x is not allowed). But I`m lazy, I don't want to write a special-judge module, so you don't have to output m pairs of i and j, just output the maximal summation of sum(i x, j x)(1 ≤ x ≤ m) instead. ^_^
Input
Each test case will begin with two integers m and n, followed by n integers S 1, S 2, S 3 ... S n. Process to the end of file.
Output
Output the maximal summation described above in one line.
Sample Input
1 3 1 2 32 6 -1 4 -2 3 -2 3
Sample Output
68 Hint Huge input, scanf and dynamic programming is recommended.
二:分析理解
最大m段子序列和问题。
设输入的数组为a[1...n],从中找出m个段,使者几个段的和为最大
dp[i][j]表示前j个数中取i个段的和的最大值,其中最后一个段包含a[j]。(这很关键) 则状态转移方程为: dp[i][j]=max{dp[i][j-1]+a[j],max{dp[i-1][t]}+a[j]} i-1=<t<=j-1 因为dp[i][j]中a[j]可能就自身一个数组成最后一段,或者a[j]与a[j-1]等前面的数组成最后一段。 此题n数据太大,二维数组开不下,而且三重循环,想到状态转移方程后还是困难重重。 想想,二维数组不行的话,肯定要压缩成一维数组: 因为dp[i-1][t]的值只在计算dp[i][j]的时候用到,那么没有必要保存所有的dp[i][j] 1<=i<=m,这样我们可以用一维数组存储。 用pre[j]表示j之前一个状态dp[i-1][]中1---j之间,不一定包含a[j]的最大字段和,然后推dp[i][j]状态时,dp[i][j]=max{pre[j-1],dp[j-1]}+a[j];三:AC代码
#include#include #include using namespace std;int dp[1000010];int pre[1000010];int a[1000010];int main(){ int m, n; int maxx; while (~scanf("%d%d", &m, &n)) { for (int i = 1; i <= n; i++) scanf("%d", &a[i]); memset(pre, 0, sizeof(pre)); for (int i = 1; i <= m; i++) { maxx = -1 << 28; for (int j = i; j <= n; j++) { dp[j] = max(dp[j - 1], pre[j - 1]) + a[j]; pre[j - 1] = maxx; if (maxx < dp[j]) maxx = dp[j]; } } printf("%d\n", maxx); } return 0;}
转载地址:https://blog.csdn.net/LaoJiu_/article/details/50986858 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2024年04月08日 02时18分00秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
系统架构设计笔记(73)—— 政府信息化与电子政务
2019-04-26
系统架构设计笔记(74)—— 企业信息化与电子商务
2019-04-26
系统架构设计笔记(75)—— 知识管理与商业智能
2019-04-26
说说在 log4j 中如何把日志记录到不同的文件中
2019-04-26
说说 jBPM 流程定义语言(3)—— state 活动 (状态活动)
2021-06-29
说说如何安装 Jenkins 2.x
2021-06-29
说说什么是 Android 的碎片(Fragment)
2021-06-29
说说如何使用 Android 的碎片(Fragment)
2021-06-29
说说 Android 碎片 (Fragment) 的生命周期
2021-06-29
运行 Tomcat, 在 Intellij IDEA 控制台输出中文乱码的解决方法
2021-06-29
说说 Android 中动态加载布局的实用技巧
2019-04-26
说说 Android 中如何实现同时兼容手机与平板的新闻应用界面
2019-04-26
说说 Android 的广播机制
2019-04-26
说说在 Android 中如何接收系统广播
2019-04-26
说说在 Android 中如何发送自定义广播
2019-04-26
说说如何使用 Android 的本地广播
2019-04-26
说说在 Android 中如何实现强制下线功能
2019-04-26
说说 jBPM 流程定义语言(8)—— sub-process(子流程活动)
2019-04-26