基础dp练习

HDU1024（m段子序列最大和，dp + 滚动数组 ）

错误思路

我一开始的思路

1
2
3
4
5
6
7
8
9
设dp[i][j]:前i个数，分为j段的最大和

dp[i][j] = max(
    dp[i-1][j] //不选第i个数
    max(dp[k][j-1] + a[i], (0 < k < i)) //第i个数独立一段
    dp[i-1][j] + a[i] //第i个数并入最后一段**
)
    
**:很明显，打了**的那个状态无法推到这个状态，因为最后一段的结尾未必是a[i-1]

正确思路思考过程

初做dp，力求搞懂，所以写下思路

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
设dp[i][j]:选取第i个数，并把前i个数分为j段的最大和（注意：a[i]必选）
    
dp[i][j] = max(
	dp[i-1][j] + a[i], //把a[i]归入最后一段
    max(dp[k][j-1] + a[i], 0 < k < i) //把a[i]独立一段
)
//简单计算，发现如上方法爆内存，且TLE
    
//优化空间
发现dp[*][j]只由dp[*][j]和dp[*][j-1]变过来，考虑用滚动数组优化
为了方便理解，把t放在第二维
顺便把a[i]提出去
优化后的条件转移方程为:
dp[t][j] = max(
	dp[t][j-1],
    max(dp[!t][k], 0 < k < j)
) + a[j]
    
//优化时间
我们知道，max(dp[!t][k], 0 < k < i)记录的是前j-1个数的最大和，我们用一个数组mmax来存储
条件转移方程变为:
dp[t][j] = max(
	dp[t][j-1],
    mmax[j-1]
) + a[j]
于是，很明显，我们可以不要t了

最终的条件转移方程为:
dp[j] = max(dp[j-1], mmax[j-1]) + a[j] //这结果是真的简单，代码也短……记得更新mmax

附上代码

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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAX_N = 1e6 + 10;
const int INF = 2e9 + 7;

int a[MAX_N];
int dp[MAX_N];
int mmax[MAX_N];

int main()
{
    int m, n, temp;
    while(scanf("%d%d", &m, &n) != EOF)
    {
        for(int i = 1; i <= n; ++i) //因为涉及mmax[j-1], 所以从下标1开始存储吧
        {
            scanf("%d", &a[i]);
        }

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

        for(int i = 0; i < m; ++i)
        {
            temp = -INF;
            for(int j = 1; j <= n; ++j)
            {
                dp[j] = max(dp[j-1], mmax[j-1]) + a[j];
                mmax[j-1] = temp;
                temp = max(dp[j], temp); //这里就是mmax[j]
            }
        }
        printf("%d\n", temp);
    }
    return 0;
}