题意：给 n 个数，找出不交叉的 m 段，使所有段内元素和最大。
设 dp[ i ][ j ]表示前 i 个数中选 j 段的最大和，其中 i 在最后一段。
这样就有两种情况：
- i 和前面的数在一段内，此时 dp[ i ][ j ] = dp[ i-1 ][ j ] + a[ i ][ j ]
- 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;
}
|