基础dp练习

基础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;
}
0%