HDU 1024 Max Sum Plus Plus ——（M段区间的最大和）

　　感觉有点奇怪的是这题明明是n^2的复杂度，n=1e6竟然能过= =。应该是数据水了。

　　dp[i][j]表示前j个数，分成i段，且最后一段的最后一个为a[j]的答案。那么转移式是：dp[i][j] = max(dp[i][j-1], max{dp[i-1][t]}) + a[j]，(i-1<=t<=j-1，j-1>=i)。前者表示在第i段的最后一个加上a[j]，后者表示a[j]另起一段。这个dp显然是可以滚动数组的，那么空间是可以接受的。然后后者可以使用一个pre数组来记录之前的最大值。具体见代码：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 using namespace std;

 const int N =  + ;

 const int inf = 2e9;

 int m,n;

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

 int main()

 {

     while(scanf("%d%d",&m,&n) == )

     {

         for(int i=;i<=n;i++) scanf("%d",a+i);

         memset(pre,,sizeof(pre));

         int temp;

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

         {

             temp = -inf;

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

             {

                 // 要加下面这行的特判，因为j和i相等的时候dp[j-1]是前一个i时候的状态

                 if(j == i) dp[j] = pre[j-] + a[i];

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

                 pre[j-] = temp; // 之所以只能这样更新是因为必须在旧状态的pre用完以后再更新新的pre

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

             }

         }

         printf("%d\n",temp);

     }

     return ;

 }

　　有几点想补充的。感觉如果用滚动数组，代码会更容易理解。个人认为上面这个特判不能少，因为j是必须大于i的，虽然少了也能过（应该是数据水了）。

另外，还是觉得这题应当是n^2规模的问题。顺便回顾一下之前一道类似的问题：选k段，每段的长度都为m，求区间的最大和。

巴特西

HDU 1024 Max Sum Plus Plus ——（M段区间的最大和）

最新文章

热门文章