HDU 1024 Max Sum Plus Plus(DP)

题目大意

---

给定序列，从中取m段，让这m段序列的和最大，这m段序列中任意两个序列不可以有重合部分。

---

题目没有给m的范围一开始烦恼了很长世间如果m很大的话应该会T,但是结果来看m应该是不大的，O(n*m)过了，一开始wa了好几发发现是数组邻界情况的没有处理好，写了个全负数数据才找出问题。

很明显状态转移为  dp[i][j] = max(dp[i][j]+num[j]，max( dp[i][i...n] )+num[j]) );

为了优化时间复杂度采用滚动数组

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAXNUM 1000005
#define INF            0x7fffffff
int num[MAXNUM];
int dp[MAXNUM];
int premax[MAXNUM][2];
int main(int argc, char const *argv[])
{
    int n, k;
    while(~scanf("%d%d",&k, &n))
    {
       int ans;
       memset(premax,0,sizeof(premax));
       memset(dp,0,sizeof(dp));
       for (int i = 1; i <= n; ++i)
            scanf("%d",&num[i]);

       for (int i = 1; i <= k; ++i)
       {
            ans = -INF;

            for (int j = i; j <= n; ++j)
            {
                dp[j] = max(dp[j-1]+num[j],premax[j-1][i&1]+num[j]);
                if(j != i)
                    premax[j][(i+1)&1] = max(premax[j-1][(i+1)&1],dp[j]);
                else 
                    premax[j][(i+1)&1] = dp[j];
               ans = max(ans,premax[j][(i+1)&1]);
           }
       }
       printf("%d\n",ans);
    }
   return 0;
}

dp的边界情况有时候真的会GG，加油吧==