Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

Day9 - E - Max Sum Plus Plus HDU - 1024

GRedComeT 2020-01-27 23:22:00 阅读数:22 评论数:0 点赞数:0 收藏数:0

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. ^_^

InputEach 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.
OutputOutput the maximal summation described above in one line.
Sample Input

1 3 1 2 3
2 6 -1 4 -2 3 -2 3

Sample Output

6
8

Hint

Huge input, scanf and dynamic programming is recommended.

思路:最大m段子段和问题,设sum[n][m]为前n个数,m段子段和的最大值,状态转移有三:
1.a[n]不属于该第m段最大和,sum[n][m] = sum[n-1][m]
2.a[n]属于该第m段最大和,且为新的一段 sum[n][m] = sum[n-1][m-1] + a[n]
3.a[n]属于该第m段最大和,且不为新的一段 sum[n][m] = sum[n-1][m] + a[n]
由状态转移方程易知,1与3互相矛盾,就要寻找第二个状态转移方程来辅助计算,令b[n][m]为包含a[n]的前n个数的m段最大子段和,则sum[n][m]为前n个数的m段最大子段和,a[n]不一定包含在内,据此知,sum[n][m] = max(b[j][m])(m<=j<=n),最终答案就是sum[n][m]
由上述分析,可得出b[n][m]的状态转移方程,a[n]属于第m段/不属于第m段,即b[n][m] = max(b[n-1][m], sum[n-1][m-1]) + a[n],通过该式可以得出计算顺序,先计算b[n][m],其中需要sum[n-1][m-1]与b[n-1][m],再更新sum[n][m]),而在计算sum[n][m] = max(b[j][m])(n<=j<=m),类比完全背包的优化,在计算sum[n][m]时,sum[n][m] = max(b[j][m])(m<=j<=n) = max(b[n][m], sum[n-1][m]),因为sum[n-1][m] = max(b[x][m])(m<=x<=n-1),等式成立,我们枚举的顺序是从小到大,所以在sum[n][m]计算之前sum[n-1][m]已经计算好了,不需要再重复枚举了
const int maxm = ;
int sum[maxm][maxm], b[maxm][maxm], a[maxm];
int main() {
ios::sync_with_stdio(false), cin.tie();
int n, m;
int tmp;
while(cin >> m >> n) {
memset(sum, , sizeof(sum)), memset(a, , sizeof(a)), memset(b, , sizeof(b));
for(int i = ; i <= n; ++i) cin >> a[i];
for(int i = ; i <= m; ++i) {
for(int j = i; j <= n; ++j) {
b[j][i] = max(b[j-][i], sum[j-][i-]) + a[j];
sum[j][i] = max(sum[j-][i], b[j][i]);
 }
}
cout << sum[n][m] << endl;
}
return ;
}
但是注意,该题的范围是1e6,二维显然空间炸了,就需要优化为一维的滚动数组形式,我们将计算的式子都列出来:
b[n][m] = max(b[n-1][m], sum[n-1][m-1]) + a[n], sum[n][m] = max(sum[n-1][m], b[n][m])
滚动时从小到大,该位置为j,则j之前的是[][m],j之后的是[][m-1](上一轮的),则先计算b[],再更新sum[],因为sum和b有冲突,先sum[n-1][m-1],再sum[n-1][m],就用一个tmp来记录
const int maxm = 1e6+;
int sum[maxm], b[maxm], a[maxm];
int main() {
ios::sync_with_stdio(false), cin.tie();
int n, m;
int tmp;
while(cin >> m >> n) {
memset(sum, , sizeof(sum)), memset(a, , sizeof(a)), memset(b, , sizeof(b));
for(int i = ; i <= n; ++i) cin >> a[i];
for(int i = ; i <= m; ++i) {
tmp = -0x3f3f3f3f;
for(int j = i; j <= n; ++j) {
b[j] = max(b[j-], sum[j-]) + a[j]; // 此处sum[j-1] 是第i-1段
sum[j-] = tmp; // 更新sum[j-1] 为第i段的, 该tmp是第i段的j-1,由上一次的循环继承而来
tmp = max(sum[j-], b[j]); // 更新tmp, 该tmp是第i段的j,为下一次循环中的的j-1
 }
sum[n] = tmp;
}
cout << sum[n] << "\n";
}
return ;
}

 

版权声明
本文为[GRedComeT]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/GRedComeT/p/12237217.html