学步园

题意：给你一串长度为n的数列，叫你求其中k段子序列的和的最大值。

本人愚笨… 画了一个晚上才搞懂怎么回事……好羞愧…

有几点领悟：博士原先讲说，DP就像填表，你先填行还是先填列都可以。现在有了更深入的理解了。

首先DP思想，对于数列中的一个数，对它进行处理，先设dp[i][j]表示前i个数（包括当前的数）j个子序列的和。有两种情况：

1.当前数的为第i个数，在前i-1个数中，若已取满j段，那么现在要做的就是把当前数纳入其中。

2.若没有取满j段，则一定取了j-1段，也就适合说当前这个数自成一段，（因为若是取的段数小于j-1段的话，就会出现要去前面的数中取段数的事情了，但是我们处理的是当前的这个数）。所以说可以列出状态转移方程：dp[i][j]=max(dp[i-1][j],dp[k][j-1])+a[i].其中，k的范围是[j-1,i-1]。因为要在前i-1个数中找到最大的和，但是序列范围肯定不能比段数来的少。嗯，所以这里dp[i-1][j]表示当前这个数只能并入前一个数的那一段区间。

然后这里有个表格，方便理解。是从  http://blog.csdn.net/skillart/article/details/8677423 这里撸的，十分感谢！从这里看懂的！

比如这么一行数据 3 6 2 3 -7 6 4 -5  所得到的f[i][j]数据如图所示

按照表格走，就觉得很好理解了。

到这里可以大致了解原理，然后剩下的就是优化了。

***********************************

没有怎么理解优化，但是这几天有事拖得太久了，先上代码吧。

#include <stdio.h>
#define maxn 1000001
#define inf 0x3fffffff;
int max(int x,int y)
{
    if(x>y) return x;
    return y;
}
int min(int x,int y)
{
    if(x>y) return y;
    else return x;
}
int n,m;
    int a[maxn],sum;
    int f[maxn],h[maxn];// help array
int main()
{

    while(scanf("%d%d",&m,&n)!=EOF)
    {
        int i,j,k;
        for(i=1;i<=n;i++)
            {
                scanf("%d",&a[i]);
                h[i]=f[i]=-inf;
            }
        for(i=1;i<=n;i++)
        {
            k=min(i,m);
            for(j=1;j<=k;j++)
            {
                f[j]=max(f[j],h[j-1])+a[i];
                h[j-1]=max(h[j-1],f[j-1]);
            }
            h[j-1]=max(h[j-1],f[j-1]);
        }
        printf("%d\n",h[m]);
    }
    return 0;
}