链接：https://vjudge.net/problem/HDU-1024
思路：强迫自己全程写不看题解，结果中间因为初始化wa了一次，状态转移没考虑完全又wa了一次。希望以后能够把这些细节全部考虑完全吧。一开始觉得有点难因为m没给范围，想了想怎么都避不开O(nm)的复杂度，那猜了一下O(nm)可能可以过，空间的话我们可以滚动数组优化，考虑描述状态，dp[i][j][k]表示选了i个数（j=0表示第i个数不选，j=1表示第i个数选，k用来滚动），那么转移的话dp[i][1][nowi^1] = max(dp[i-1][0][nowi],dp[i][1][nowi],dp[i][1][nowi])+a[i] (注意即使之前选了也可以强制分成在本次操作中加一次分割次数)，dp[i][0][nowi^1] = max(dp[i][0][nowi],dp[i][1][nowi])，注意初始化状态即可。
代码：
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
|
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+100;
ll dp[maxn][2][2];
int a[maxn];
int n,m;
int main(){
while(~scanf("%d%d",&m,&n)){
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
dp[i][0][0] = dp[i][0][1] = -1e18;
dp[i][1][0] = dp[i][1][1] = -1e18;
}
dp[0][0][0] = dp[0][0][1] = 0;
dp[0][1][0] = dp[0][1][1] = 0;
int nowi = 0;
if(m>n)m = n;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dp[j][1][nowi^1] = max(dp[j-1][1][nowi],max(dp[j][1][nowi],dp[j-1][0][nowi]))+a[i];
dp[j][0][nowi^1] = max(dp[j][0][nowi],dp[j][1][nowi]);
}
nowi^=1;
}
long long res = max(dp[m][0][nowi],dp[m][1][nowi]);
printf("%lldn",res);
}
return 0;
}
|
近期评论