HDU 1024 Max Sum Plus Plus（dp）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1024

题目大意：有多组输入，每组一行整数，开头两个数字m,n，接着有n个数字。要求在这n个数字上，m块数字的最大和。比如2 6 -1 4 -2 3 -2 3，就是（4 -2 3）和（3）这两块最大和为8。

解题思路：当成有m层，我们可以设置两个数组dp,mpre。dp[j]记录当前这一层包含a[j]时的最大值(包含a[j])，mpre[j]个记录上一层到第j-1个位置时的最大和（不一定包含a[j]）。这样写出状态转移方程dp[j]=max(dp[j-1],mpre[j-1])+a[j]。表示选择接着这一层j上一个+a[j],或这上一层j-1这个位置取最大值的状态+a[j]。

举个例子2 8 -1 4 -2 3 -10 3 -2 3，在i=2,j=8时，此时dp[8]=max(dp[7],mpre[7])。dp[7]=6表示（4 -2 3）+（3 -2）这两块的和,mpre[7]=5表示（4 -2 3）这一块的和，选择dp[8]=dp[7]+a[j]=0相当于（4 -2 3）+(3 -2 3)这两块的和。

推广一下，在第m层时，mpre[j-1]表示在j-1这个位置m-1块的最大和，如果选择mpre[j-1]+a[j]相当于a[j]为一块，mpre[j-1]为m-1块加起来就是j位置m块时的最大值。

同理dp[j-1]是包含了a[j-1]的在j-1这个位置m块的最大和，如果选择dp[j-1]+a[j]相当于a[j],a[j-1]....一直到上一次选择mpre为止算一块(或者到第m-1个，可能没有选择过mpre),前面的有m-1块，加起来也是j位置m块时的最大值。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 typedef long long LL;

 const int N=1e6+;

 const LL inf=1e18;

 LL a[N],dp[N],pre[N];

 int main(){

     int m,n;

     while(~scanf("%d%d",&m,&n)){

         memset(dp,,sizeof(dp));

         memset(pre,,sizeof(pre));

         for(int i=;i<=n;i++)

             scanf("%lld",&a[i]);

         LL tmp;

         for(int i=;i<=m;i++){

             tmp=-inf;

             for(int j=i;j<=n;j++){

                 dp[j]=max(dp[j-]+a[j],pre[j-]+a[j]);

                 pre[j-]=tmp;

                 tmp=max(tmp,dp[j]);

             }

         }

         printf("%lld\n",tmp);

     }

     return ;

 }

巴特西

HDU 1024 Max Sum Plus Plus（dp）

最新文章

热门文章