Max Sum Plus Plus HDU - 1024

题目链接
题意：给你一个n,m，求序列长度为n的序列n中找到m个区间，要求m个区间和最少，求区间和的大小。
题解：我们分析题目，整体的数组长度为n，我们需要将数组中m个区间和加起来最大（区间不相交）。所以有两个状态，一是n,二是m，所以是二维的dp。我们可以将dp[i][j]表示为在前j个数中找，将j个数分解成i部分，且最后一个数是a[j]，这样我们可以找到状态方程 dp[i][j]=max(dp[i][j-1]+a[j],dp[i-1][k]+a[j]) 其中dp[i-1][k]表示之前的长度的最大值。其中dp[i][j-1]表示j承接之前的数组，dp[i-1][k]表示找到之前的最大值然后另开辟一个区间，这样找是正确的。这样两维的情况下可能会爆内存，爆时间（三维的），所以我们应该要优化代码，这里我们可以优化的是dp[i-1][k]就是前面过程中的分成i-1段的最大值，所以我们动态的维护一个最大值即可。
下面是AC代码：

#include
#include
#include
#include
using namespace std;
const int N=1e6+10;
const int inf=0x3f3f3f3f;
int a[N],dp[N],maxx[N];
signed main()
{
    int n,m;
    while(~scanf("%d%d",&m,&n))
    {
        //memset(pre_max,0,sizeof(pre_max));
        //memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++) maxx[i]=0;
        for(int i=1;i<=n;i++) dp[i]=0;
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        int mx;
        for(int i=1;i<=m;i++)//这里n,m两个维度的顺序是不能互换的，因为如果换了的话，正常的3维是可以的，但是优化的是不行的，因为额这样的话我就没办法保存前一段的最大值。
        {
            mx=-inf;
            for(int j=i;j<=n;j++)//这里只需要从i开始，因为分成i部分至少要i个数，这里空间优化类似于01背包，但并不是完全相同的，因为这里实际上是于背包不同的，背包实际上是两维的，这里实际上是三维的变成两维的了，直接优化了一维，所以在优化的时候一定要小心，在理解的前提下优化.
            {
                dp[j]=max(dp[j-1],maxx[j-1])+a[j];
                maxx[j-1]=mx;//这里是存取被分成i段时的最大值，方便进行i+1段时的dp
                mx=max(dp[j],mx);//这里取最大，保证之后的mx是最大的，这里其实初始化暗藏初始化，就是每次mx初始化为-inf就是为了将表示将i-1分成i-1段时是不可能的
            }
        }
        printf("%d\n",mx);
    }
    return 0;
}

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

总结：dp问题解答出来的关键一步就是分析状态，这里就是需要两个状态（n,m），然后对状态赋予恰当的定义（即状态表示），这样就可以正确的写出转移方程。而且在想状态表示的时候一定要从小想起，如果一开始就想普遍情况下的话，是很难想到的，而且在写dp的过程中不是知道转移方程后实际上是不需要还原过程的，dp的还原和递归类似，很难还原，因为他是一个动态的过程，所以我们没必要取还原过程，正确的表示状态后，写出转移方程后就能得到答案，dp的过程其实是实际过程的虚拟化，我们不必去还原过程