web analytics

HDU1024 Max Sum Plus Plus DP

题目链接: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]时会用到。

但是呢,题目空间开不下。

我们的代码如下:

我们发现其中dp[i][j-1]为上一个状态.

所以我们可以将dp[i][j]可以化成一个变量,然后每次反复循环使用。

以上.

参考文献:

http://www.cnblogs.com/dongsheng/archive/2013/05/28/3104629.html

Post a Comment

You must be logged in to post a comment.