HDU - 1024 Max Sum Plus Plus (kuangbin - 基础DP)

题目描述 (已转换成中文)

  你有n个数s1, s2…sn，给你一个整数m，求m个子段和的最大值

输入格式

  输入m，输入n。后面跟着输入n个ai (n < 1e6)

输出格式

  输出最大和

输入输出样例

输入

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

输出

6 8

题目链接

分析：

  这道题大概的意思就是把n个数中，切成m段，求这m段的最大字段和，属于动态规划的题目，重点是找出转移方程。   先来分析下如何得到状态方程：使用一个二维数组dp[i][j]表示如果取第j个数时，前j个数(包括第j个数)划分成i段的最大值，所以此时会出现两种情况：(1)､第j个数直接被并到第i段里边，此时的转移方程：dp[i][j] = d[i][j - 1] + a[j] ; (2)､第j个数没有被划分进第i段内，即第j个数独自成为第i段，既然第j个元素没有被划分在第i段内，说明前j - 1个元素被划分成了i - 1段。被划分成i - 1段至少需要i - 1个元素，最多j - 1个元素。(因为当前只有j - 1个元素可用)。所以此时需要枚举从i - 1开始，到j - 1结束这些状态，求出这些数划分成i - 1段时，哪种状态得到的i - 1个子段的和是最大的。所以此种情况的转移方程：dp[i][j] = max(dp[i - 1][k]+ a[j])，k满足：i - 1 <= k <= j - 1。综合两种情况，动态转移方程： dp[i][j] = max(dp[i][j - 1] + a[j], max(dp[i - 1][k] + a[i]));

这道题需要注意的地方：

  但是这个做法会产生一个问题，DP时的时间复杂度的O(n ^ 3)，n的数据范围是1e6，如果直接暴力得到二维数组dp，绝对会超时，所以我们需要dp做法进行优化，由前面的分析我们得到的动态转移方程式：dp[i][j] = max(dp[i][j - 1] + a[j], max(dp[i - 1][k] + a[i]))，我们发现每一次得到dp[i][j]时，max(dp[i - 1][k] + a[k])中有用到的只有前i - 1段的dp数组，就是在遍历找上一个状态被划分成i - 1段之后的最大值，那么可以进行优化了，在每一次递推得到dp[i][j]的时候，专门使用一个b数组记录一段数中的最大dp值(b[j]表示在前j个数划分成i个子段时的最大和)，所以这样在下一层循环中(第i++层)，通过b[j - 1] + a[j]就可以表示前j - 1个数被分成前i - 1段并且第j个数独自成为一段时的最大子段和(上述的第二种情况)，这样就优化了一层for循环。时间复杂度下降了一个维度。对于状态方程：dp[i][j] = max(dp[i][j - 1] + a[j], max(dp[i - 1][k] + a[i]))中的dp[i][j - 1] + a[i]可以直接表示成dp[j - 1] + a[i]，所以，最终的转移方程：dp[i] = max(dp[i - 1] + a[i], b[i - 1] + a[i]))，然后再加上我们需要维护的一些信息，更新即可。

列举两个图来方便理解：

具体的转移方程是这样得来的：

代码如下：

#include <bits/stdc++.h> using namespace std; typedef long long LL; int read(){ int x, f = 1; char ch; while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1; x = ch - '0'; while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48; return x * f; } int dp[1000005], a[1000005], b[1000005]; //a数组是保存每一个具体的数据 //b数组保存的是前i - 1段的最大子段和，b[j - 1]代表前j - 1个数划分为i - 1 段的最大子段和 //dp数组保存前j个数的最大子段和 int main(){ int n, m, i, j, s; while (~scanf("%d%d", &m, &n)){ for(i = 1; i <= n; i++){ a[i] = read(); dp[i] = b[i] = 0; //初始化dp数组和保存前i - 1段的最大子段和的b数组 } for(i = 1; i <= m; i++){ s = -1e9; for (j = i; j <= n; j++){ dp[j] = max(dp[j - 1] + a[j], b[j - 1] + a[j]); //更新dp数组，求得此时前j个数被分为i段的最大子段和 b[j - 1] = s; //更新b数组，保存前j - 1个数被分为i段的最大子段和，以便后续循环(i++)中，保存j - 1个元素被划分为i - 1段时的最大子段和 s = max(s, dp[j]); //不断更新最大子段和，在下一层循环中赋值给b[j - 1] } } printf("%d\n", s); } }