HDU1024 Max Sum Plus Plus(DP)

题目链接

题意:给n个数,找出不交叉的m段,使所有段内元素和最大。

设dp[ i ][ j ]表示前 i 个数中选 j 段的最大和,其中 i 在最后一段。

这样就有两种情况:

  1. i 和前面的数在一段内,此时dp[ i ][ j ] = dp[ i-1 ][ j ] + a[ i ][ j ]

  2. i 自己单独一段,此时dp[ i ][ j ] = max( dp[ k ][ j-1 ] ) + a[ i ][ j ] , 其中 j-1 =< k <=i-1 .

这样就写出了状态转移方程:dp[ i ][ j ] = max ( dp[ i-1 ][ j ] , max( dp[ k ][ j-1 ] ) ) + a[ i ][ j ], j-1 =< k <=i-1 .

此题n高达10^6,开二维数组空间肯定不够,观察状态转移方程,其中dp[ ][ j ]只用到了dp[ ][ j ]和dp[ ][ j-1 ],也就是说dp[ ][ 0 ]~dp[ ][ j-2 ]的值都不用了,也就是说 j 只开二维的就够了(听说叫滚动数组)。

再来看一看时间复杂度:n*n*m,再来观察方程,带 k 的这重循环是为了找最大值,这可以同步完成,避免了这层循环。时间复杂度为n*m.

?
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
#include<iostream>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<map>
#include<stack>
#include<set>
#include<cstdio>
#include<algorithm>
using namespace std;
 
int a[1000005];
int dp[1000005][2];
 
int main(){
    //freopen("a.txt", "r", stdin);
    int n, m;
    while(scanf("%d %d", &m, &n) != EOF){
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        int ans = -1e9;
        for(int j = 1; j <= m; j++){
            int maxx = -1e9;
            for(int i = j; i <= n; i++){
                maxx = max(maxx, dp[i-1][0]);
                dp[i][1] = max(dp[i-1][1], maxx) + a[i];
                if(j == m) ans = max(ans, dp[i][1]);
            }
            for(int k = 0; k <= n; k++)
                dp[k][0] = dp[k][1];
        }
        cout << ans << endl;
    }
    return 0;
}
Zhao Li /
Published under (CC) BY-NC-SA in categories 算法  tagged with 动态规划