题目链接:

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
*/
05-11 22:39