1052 最大M子段和(DP)

基准时间限制：2 秒空间限制：131072 KB 分值: 80 难度：5级算法题

N个整数组成的序列a[1],a[2],a[3],…,a[n]，将这N个数划分为互不相交的M个子段，并且这M个子段的和是最大的。如果M >= N个数中正数的个数，那么输出所有正数的和。

例如：-2 11 -4 13 -5 6 -2，分为2段，11 -4 13一段，6一段，和为26。

Input

第1行：2个数N和M，中间用空格分隔。N为整数的个数，M为划分为多少段。（2 <= N , M <= 5000)

第2 - N+1行：N个整数 (-10^9 <= a[i] <= 10^9)

Output

输出这个最大和

Input示例

Output示例

26

//题意有点难懂，应该是说，从 N 个数中，选出小于等于 M 段，不相交，并且和最大
显然dp题，但怎么设计比较难，假设划分成 x 段，对于每个元素，有这样的考虑，
1、和上一个连起来，就是上一个位置分为 x 段
2、或者新开一段，就是上一个位置分 x-1 段
那么, dp[i][j] 表示前 i 个数选出 j 段，并且最后一段有 dat[i] 
dp[i][j] = max(dp[i-1][j] , dp[j-1 -- i-1][j-1]) 
然后发现这是 n^3 ，得优化一下
dp[j-1 -- i-1][j-1] 这个可以用一个数组存一下，
设为 pre[i][j] ,表 前 i 个数，选出 j 段的最大和
pre[i][j] = max(pre[i-1][j],dp[i][j])
然后可以发现，最多和 j-1 有关，所以可以滚动一下优化空间，就可以愉快的dp辣

 #include <bits/stdc++.h>

 using namespace std;

 #define MOD 1000000007

 #define INF 0x3f3f3f3f

 #define eps 1e-9

 #define LL long long

 #define MX 5005

 int n,k;

 int dat[MX];

 LL dp[MX][];

 LL pre[MX][];

 int main()

 {

     while(scanf("%d%d",&n,&k)!=EOF)

     {

         dp[][]=, pre[][]=;

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

         {

             scanf("%d",dat+i);

             pre[i][]=;

             dp[i][]=;

         }

         LL ans =;

         for (int j=;j<=k;j++)

         {

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

             {

                 dp[i][j&] = max(dp[i-][j&],pre[i-][(j-)&])+dat[i];

                 pre[i][j&] = max(pre[i-][j&],dp[i][j&]);

             }

             ans = max(ans,pre[n][j&]);

         }

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

     }

     return ;

 }