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 ;
}```

https://www.cnblogs.com/GRedComeT/p/12237217.html