(动态规划)Max Sum Plus Plus--hdu--1024
http://acm.hdu.edu.cn/showproblem.php?pid=1024
Max Sum Plus Plus
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 21363 Accepted Submission(s): 7144
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. ^_^
Process to the end of file.
w[i][j]: 前 j 个数分为 i 段, 第 j 个数必须选;1. 第 j 个数单独为1段;2. 第 j 个数与前面的数连一块。
w[i][j] = max(b[i-1][j-1], w[i][j-1]) + a[j];
b[i][j]:前 j 个数分为 i 段, 第 j 个数可选可不选; 1.选第 j 个数;2.不选第 j 个数。
b[i][j] = max(b[i][j-1], w[i][k]);
/// w[j] 表示 j 个元素取 i 段, a[j] 必须取是的最大值
w[j] = max(dp[1-t][j-1], w[j-1]) + sum[j]-sum[j-1];
/// dp[t][j] 表示在a[j]可取可不取这两种情况下取得的最大值
dp[t][j] = max(dp[t][j-1], w[j]);
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 1000001
using namespace std; int sum[N], w[N], dp[][N]; ///sum[i] 里面存的是前 i 项和 int main()
{
int m, n; while(scanf("%d%d", &m, &n)!=EOF)
{
int i, j, x; sum[] = ;
for(i=; i<=n; i++)
{
scanf("%d", &x);
sum[i] = sum[i-] + x;
dp[][i] = ; ///从前 i 个元素中取 0 段, 最大值为 0
} /** 我们先假设a[i]中 存放该序列的第 i 个值,
w[i][j] 表示前 j 个数分为 i 段, 第 j 个数必须选这种情况下取得的最大值
b[i][j]表示在前 j 个数中取 i 段 这种情况写取得的最大值 w[i][j]: 前 j 个数分为 i 段, 第 j 个数必须选;1. 第 j 个数单独为1段;2. 第 j 个数与前面的数连一块。
w[i][j] = max(b[i-1][j-1], w[i][j-1]) + a[j];
b[i][j]:前 j 个数分为 i 段, 第 j 个数可选可不选; 1.选第 j 个数;2.不选第 j 个数。
b[i][j] = max(b[i][j-1], w[i][j]); **/ int t=;
for(i=; i<=m; i++) /// i表示取 i 段
{
for(j=i; j<=n; j++) /// 如果dp[i][j](j<i)是没有意义的
{
if(i==j)
dp[t][j] = w[j] = sum[j];
else
{
/// w[j] 表示 j 个元素取 i 段, a[j] 必须取是的最大值
w[j] = max(dp[-t][j-], w[j-]) + sum[j]-sum[j-];
/// dp[t][j] 表示在a[j]可取可不取这两种情况下取得的最大值
dp[t][j] = max(dp[t][j-], w[j]);
}
}
t = -t; ///t在 0 和 1 直间交替变换 /** 为什么要交换呢??? 这是为了要节省空间
仔细观察递归式
w[i][j] = max(b[i-1][j-1], w[i][j-1]) + a[j];
b[i][j] = max(b[i][j-1], w[i][j]);
我们发现,对于取 i 段, w[i][j] 只与 b[i-1][k-1] 和 w[i][k-1] 有关, 与之前的那一些项没有关系
因此我们的数组可以开小一点, 用更新来覆盖掉前面的值!!! **/
} printf("%d\n", dp[m%][n]);
}
return ;
}
最新文章
- bzoj 2301: [HAOI2011]Problem b
- C/C++ 堆和栈的区别
- 解析txt文本,dom4j工具输出为xml文档
- JavaScript 字符 &;quot;转换
- 阿里巴巴分布式服务框架Dubbo介绍(1)主要特色
- Unity3D 角色(物体) 移动方法 合集
- jira部署,主机迁移,数据库迁移,jira
- bzoj 1038 [ZJOI2008]瞭望塔(半平面交)
- C栈stack
- JSON数据的中文乱码问题
- ASP.ENT中上一篇和下一篇
- Mobile Service更新和 Notification Hub 对Android的支持
- Fibonacci(数论 输出前四位Fibonacci)
- J - 今年暑假不AC
- Spring设置定时任务时,关于执行时间的规则设置
- [转]迄今为止最优的Eclipse运行性能调优 ,含eclipse.ini
- 前端 - jquery方式 / iframe +form 方式 上传文件
- Hbase理论&;&;hbase shell&;&;python操作hbase&;&;python通过mapreduce操作hbase
- python面向对象封装案例(附:is和==的区别)
- Instruments(性能调优 12.3)