hdu 1024 Max Sum Plus Plus (动态规划)
2024-10-03 23:44:40
Max Sum Plus Plus
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 37418 Accepted Submission(s): 13363
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 37418 Accepted Submission(s): 13363
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.
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 S1, S2, S3, S4 ... Sx, ... Sn (1 ≤ x ≤ n ≤ 1,000,000, -32768 ≤ Sx ≤ 32767). We define a function sum(i, j) = Si + ... + Sj (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(i1, j1) + sum(i2, j2) + sum(i3, j3) + ... + sum(im, jm) maximal (ix ≤ iy ≤ jx or ix ≤ jy ≤ jx 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(ix, jx)(1 ≤ x ≤ m) instead. ^_^
Input
Each test case will begin with two integers m and n, followed by n integers S1, S2, S3 ... Sn.
Process to the end of file.
Each test case will begin with two integers m and n, followed by n integers S1, S2, S3 ... Sn.
Process to the end of file.
Output
Output the maximal summation described above in one line.
Output the maximal summation described above in one line.
Sample Input
1 3 1 2 3
2 6 -1 4 -2 3 -2 3
1 3 1 2 3
2 6 -1 4 -2 3 -2 3
Sample Output
6
8
6
8
Hint
Huge input, scanf and dynamic programming is recommended.
C/C++:
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std; const int MAX = 1e6 + ; int m, n, pre[MAX], dp[MAX], num[MAX], ans, j; int main()
{
while (~scanf("%d%d", &m, &n))
{
memset(dp, , sizeof(dp));
memset(pre, , sizeof(pre)); for (int i = ; i <= n; ++ i) scanf("%d", &num[i]);
for (int i = ; i <= m; ++ i)
{
ans = -INF;
for (j = i; j <= n; ++ j)
{
dp[j] = max(dp[j - ], pre[j - ]) + num[j];
pre[j - ] = ans;
ans = max(dp[j], ans);
}
// pre[j - 1] = ans;
} printf("%d\n", ans);
}
return ;
}
最新文章
- MVC4做网站后台:栏目管理1、添加栏目
- 如何使用抓包工具fiddler对app进行接口分析
- sencha gridpanel改变单元格颜色
- html实体字符
- Android Studio Check for Update
- Asp.net使用jQuery实现数据绑定与分页
- ListView simpleAdapter的基本使用
- Axure RP 8.0正式版下载地址 安装和汉化说明
- mysql读写分离
- c++ STL容器适配器
- jedis &; common pool
- NGINX+PHP+ZABBIX,推荐
- Django--文件上传和下载,自测试可用
- Linux查看用户属于哪些组/查看用户组下有哪些用户
- 洛谷P4069 [SDOI2016]游戏(李超线段树)
- 移动端二三事【三】:transform的矩阵(matrix)操作、transform操作函数及注意事项
- jstl格式化页面显示科学计数法问题
- Scala学习笔记(四)—— 数组
- 浅析C语言中assert的用法(转)
- TSQL--时间类型和毫秒数转换