HDU 1024 (不重叠m段最大和) Max Sum Plus Plus

时间：2021-05-14 01:54:49

题解是看的这里的：

http://www.acmerblog.com/hdu-1024-Max-Sum-Plus-Plus-1276.html

当前这个状态是dp[i][j]，i 表示当前的段，j表示前j个数组成了当前的这i个段的最大值，而且a[j]在最后一个段中

  • 状态dp[i][j]可以从dp[i][j-1]转移过来，表示第j个数字正好可以和 i 个段的前j-1个数字相加的和是当前所在状态中最大的
  • 状态dp[i][j]可以从dp[i-1][j-1]转移过来，表示第 j 个数字正好可以成为第 i 个段，并且使得和i-1个段相加的和是当前所有状态中最大的

注意在第26行和第30行代码更新dp以后，其含义变成前i个段前j个数构成和的最大值，而a[j]并不一定要在这些段中，反正从这个状态转移过去的时候a[j+1]自成一段，与a[j]无关

最最头疼的就是DP过程中状态的含义会发生变化，Orz

现在看来kuangbin大神说的到清楚一些，不过他的代码的变量命名方式是在不敢恭维，=_=||

http://www.cnblogs.com/kuangbin/archive/2011/08/04/2127085.html

 //#define LOCAL

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int maxn =  + , INF = ( << );

 int dp[][maxn], a[maxn], m, n;

 int main(void)

 {

     #ifdef LOCAL

         freopen("1024in.txt", "r", stdin);

     #endif

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

     {

         int i, t;

         memset(dp, , sizeof(dp));

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

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

         for(i = , t = ; i <= m; ++i, t =  - t)

         {

             dp[t][i] = dp[-t][i-] + a[i];

             dp[-t][i] = max(dp[-t][i], dp[-t][i-]);

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

             {

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

                 dp[-t][j] = max(dp[-t][j], dp[-t][j-]);        //此次更新以后dp[1-t][j]存放的是前j个数分成i-1段的最大值，并不要求a[j]在其中

             }

         }

         int ans = -INF;

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

             ans = max(ans, dp[m&][i]);

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

     }

     return ;

 }

代码君

相关文章