题目链接
HDU-1024
思路
动态规划，d[i][j]表示在选取第j个数字的情况下，将前j个数字分成i组的最大和， 考虑第j个数字加入，得到状态转移方程
dp[i][j]=max(dp[i][j-1],dp[i-1][i-1~j-1])+num[i];
前面部分就是把当前这个数与前面一个子序列连续起来，后面一个则是另起一个序列
但是这样会造成超内存，所以需要优化，很显然，观察上面的式子
dp[i]只与dp[i-1]相关，所以前面的dp[i][j-1]->dp[j-1],用循环滚掉了，然后后面的一部分我们发现我们只需要维护最大值一起参加循环滚动就好了，所以维护一个最大值就可以省掉一维的空间最后状态转移方程变为
dp[j]=max(dp[j-1],pre[j-1])+num[i];
代码实现
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6+10;
const int inf = 1e9+10;
int num[N];
int dp[N];
int pre[N];
int main()
{
int n,m,tem;
while(scanf("%d %d",&m,&n)!=EOF)
{
for(int i=1;i<=n;i++)scanf("%d",&num[i]);
memset(dp,0,sizeof(dp));
memset(pre,0,sizeof(pre));
for(int i=1;i<=m;i++)
{
tem = -inf;
for(int j=i;j<=n;j++)
{
dp[j]=max(dp[j-1],pre[j-1])+num[j];
pre[j-1]=tem;
tem=max(tem,dp[j]);
}
}
cout<<tem<<endl;
}
}
|