HDU-1024 Max Sum Plus Plus

Posted on | Edited on | In | Views:

题意

给你一个序列n个数组成，然后让你在里面找到m个子序列，让这m个子序列的和最大。

题解

$dp[i][j]$表示的是第j个数字在第i个子序列时的当前最优值。
$dp[i][j] = maxx(dp[i][j-1] + num[j] ,maxx(dp[i-1][k]) + num[j])$，k是从1到 $j-1$.
可以这么理解这个转移方程，对于当前的这个数字，如果把他放到第i个子序列中有两种情况，一个是他作为第i个子序列的第一个数字，另一个就是不作为第一个数字，作为第一个数字的时候是 $max(dp[i-2][k] + num[j]) ,1<=k<i $的意思是从之前的所有中找到 $i-1$ 个子序列的最大值+当前的值，不做为第一个的时候那么他前面的那个数字一定是i序列的，同一个子序列，又不是作为第一个，那么前面的那个货就一定是同一个子序列的，那么当前的值是$dp[i][j-1] + num[j]$,在两种决策中选择一个最有的就行了，还有就是$max(dp[i-1][k]+num[j])$的这个地方可以开一个数组记录下来，不能每次都跑，跑不起，再有就是这个题目没有给m的范围，所以开不了二维数组（目测不是很大，大的话会超时，但是肯定是先超内存在超时，所以为了保险，还是吧$dp[][]$压缩成一维的）那么状态转移就边成这样了$dp[j]$表示的是 j这个人在当前的这个子序列中的最优值，mk[j]表示的是在上一个子序列中1—j的dp的最大值，所以就变成 $dp[j] = maxx(dp[j-1] + num[j] ,mk[j-1]+num[j])$;还是 max(作为i个子序列的第一个元素，不是第一个元素取一个最大值)。在解释下代码的核心部分。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <fstream>
#include <ctime>
#include <strstream>
#define ull unsigned long long
#define ll long long
#define inf 0x3f3f3f3f
#define mod (int)1e9+7
#define for0(i, n) for (int i = 0; i < n; i++)
#define for1(i, n) for (int i = 1; i <= n; i++)
#define forl(i, l, r) for (int i = l; i <= r; i++)
#define forn(i, n) for (int i = n; i >= 0; i--)
#define mem0(a) memset(a, 0, sizeof(a))
#define mem_1(a) memset(a, -1, sizeof(a))
#define meminf(a) memset(a, inf, sizeof(a))
using namespace std;


int d[1000006],a[1000006],pre_max[2][1000006];
int main()
{
    int n,m;

    while (cin>>m>>n) {
        memset(d, 0, sizeof(d));
        memset(pre_max, 0, sizeof(pre_max));
        for (int i=1; i<=n; i++) scanf("%d",&a[i]);
        int maxx;
        //pre_max[0][0]=-99999999;pre_max[1][0]=-99999999;
        for (int i=1; i<=m; i++) {
            maxx=-9999999;
            for (int j=i; j<=n; j++) {
                d[j]=max(d[j-1]+a[j], pre_max[(i+1)%2][j-1]+a[j]);
                maxx=max(maxx, d[j]);
                pre_max[i%2][j]=maxx;
            }
        }
        cout<<pre_max[m%2][n]<<endl;
    }
    return 0;
}