HDU 1024 A - Max Sum Plus Plus DP + 滚动数组

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

刚开始的时候没看懂题目,以为一定要把那n个数字分成m对,然后求m对中和值最大的那对

但是不是,题目说的只是选出m对,所以有些数字是可以不用的。

那么就用

dp[i][j]表示前j个数,分成了i段,其中第a[j]个数必定包含在第i段之中的最大和值。就是a[j]必定选了而且在第i段之中。

至于为什么要这样设。

1、如果想得到ans,只需要扫描一次ans = max(ans, dp[m][m....n]),因为第m段肯定是以a[]中某个数字结尾。同时至少要有m个数才能分成m段

2、更多的是看做题量,很多dp都是这样设,(最大字段和等)。所以dp靠得还是经验,我还是去多多刷题补上我的弱项----dp

转移:

对于每个a[j],要么,a[j]独立一组(独立在第i组上),所以此时的贡献是max(dp[i - 1][k]) + a[j],其中 i - 1 <= k <= j - 1

k为什么要大于等于i - 1呢,因为起码要有i - 1个数才能组成i - 1组。然后选取最大的来和a[j]组合成i个组。

要么, a[j]在第i组上但是a[j - 1]也在第i组上(这样是用来判断和前面的连接成一个组的) 贡献:dp[i][j - 1] + a[j]

直接转移m * n * n

考虑到第一个转移的时候,肯定是从dp[i - 1][k]中选一个最大的来和a[j]相加,所以考虑到用个preMx[j]表示前j个数在分成i - 1个组时候的最大值。能压缩成n * m

因为dp只和上一维有关,故可以用滚动数组压缩空间、

滚动数组就是,

例如现在要算分成i个组的,那么你分成i - 2个组的已经没用了,故可以舍弃

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = + ;
LL dp[maxn];
LL preMx[][maxn];
int a[maxn];
int n, m;
void work() {
for (int i = ; i <= n; ++i) {
preMx[][i] = ;
preMx[][i] = ;
dp[i] = ;
}
for (int i = ; i <= n; ++i) scanf("%d", &a[i]);
int now = ;
LL mx;
for (int i = ; i <= m; ++i) {
mx = -inf;
for (int j = i; j <= n; ++j) { //因为分成i组,起码要有i个数
dp[j] = max(preMx[!now][j - ] + a[j], dp[j - ] + a[j]);
mx = max(mx, dp[j]);
preMx[now][j] = mx;
}
now = !now;
}
printf("%I64d\n", mx);
}
int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
while (scanf("%d%d", &m, &n) != EOF) work();
return ;
}
上一篇:黑马程序员 SaveFileDialog的跨线程调用 (专题三)


下一篇:9.Methods(二)