题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1024
题目大意:
给你一串n个数序列让你选m个互不相等的子串。使他们和最大。
分析:
我们设dp[i][j]表示序列中前j项得到含i个子串的最大值,且最后一个子串以j为结尾。
那么dp[i][j]可以从以下几个方式生成:
1,将j加入上一个子串中。
2,将j独立成段.
所以DP方程就是
然而我们发现这个方程需要处理dp[i-1][t]这个量，所以复杂度会很高。
会达到O(n^2)的样子。
于是乎。发现其实我们只需要每次去维护dp[i-1][i-1]到dp[i-1][j]的最大值就好。
于是我们定义 pre_max[]
其中pre_max[j-1]表示dp[i-1][i-1]到dp[i-1][j]的最大值。
于是DP方程改为了
但是pre_max[n]这个变量始终都用不到。
所以由于每次求dp[i][j]时都会更新pre_max[j].但是由于我们在求dp[i][j+1]的时候会访问到pre_max[j]所以我们需要将dp[i][j]暂时存一下。存到pre_max[n]中。之后等运行到dp[i][j+2]时我们就用不到pre_max[j]了。反而到dp[i+1][j+1]时会用到。
但是呢，题目空间开不下。
我们的代码如下:
|
1 2 3 4 5 |
for i to m for j to n dp[i][j]=max(per_max[j-1],dp[i][j-1])+num[j]; pre_max[j-1]=pre_max[n]; pre_max[n]=max(pre_max[n],dp[i][j]); |
我们发现其中dp[i][j-1]为上一个状态.
所以我们可以将dp[i][j]可以化成一个变量，然后每次反复循环使用。
以上.
|
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 40 41 42 43 |
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int pre_max[1000001]; int num[1000001]; int temp,n,m; int dp() { for(int i=1;i<=m;++i) { temp=0; for(int k=1;k<=i;++k) { temp+=num[k]; } pre_max[n]=temp; for(int j=i+1;j<=n;++j) { temp=max(pre_max[j-1],temp)+num[j]; pre_max[j-1]=pre_max[n]; pre_max[n]=max(temp,pre_max[n]); } } printf("%d\n",pre_max[n]); return 0; } int main() { while(~scanf("%d%d",&m,&n)) { memset(pre_max,0,sizeof(pre_max)); for(int i=1;i<=n;++i) { scanf("%d",&num[i]); } dp(); } return 0; } |
参考文献:
http://www.cnblogs.com/dongsheng/archive/2013/05/28/3104629.html
