HDU 1024 Max Sum Plus Plus【DP，最大m子段和】

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1024

题意：

给定序列，给定m，求m个子段的最大和。

分析：

设dp[i][j]为以第j个元素结尾的i个子段的和。

对于每个元素有和前一个元素并在一起构成一个子段，和单独开启一个子段两种可能，状态转移方程

dp[i][j] = max(dp[i][j - 1], dp[i - 1][k]) + a[j] (k >= i - 1 && k <= j - 1)

时间复杂度O(m∗n2)，n高达1e6，肯定超时。

接着可以用滚动数组进行空间和时间的优化。

直接开一个数组存储这个 dp[i−1][k]，也就是前j个元素中子段数为i - 1的最大值，用ans记录当前数目子段的最大值，然后子段数不断增加的过程中不断更新。时间复杂度O(n∗m)。

我觉得ans和数组dp，t都应该long long的，发现int也能A。。。

代码：

#include<cstdio>

#include<cstring>

#include<iostream>>

using namespace std;

#define sa(a) scanf("%d", &a)

#define sal(a) scanf("%I64d", &a)

const int maxn = 1e6 + 5, INF = 0x3f3f3f3f;

int a[maxn];

long long dp[maxn], t[maxn];

int main (void)

{

    int n, m;

    while(~scanf("%d%d", &m, &n)){

        memset(dp, 0, sizeof(dp));

        memset(t, 0, sizeof(t));

        for(int i = 1; i <= n; i++)  sa(a[i]);

        long long ans;

        for(int i = 1; i <= m; i++){

            ans = -INF;

            for(int j = i; j <= n; j++){

                dp[j] = max(dp[j - 1], t[j - 1])+ a[j];

                t[j - 1] = ans;

                ans = max(ans, dp[j]);

            }

        }

        printf("%d\n", ans);

    }

    return 0;

}

/*

1 2 2 3

3 3 -3 -3 -3

*/