51nod 1052 最大M子段和

旧城等待， 2021-12-10 03:21 331阅读 0赞

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。

收起

# 输入 #

第1行：2个数N和M，中间用空格分隔。N为整数的个数，M为划分为多少段。（2 <= N , M <= 5000)
    第2 - N+1行：N个整数 (-10^9 <= a[i] <= 10^9)

# 输出 #

输出这个最大和

# 输入样例 #

7 2
    -2
    11
    -4
    13
    -5
    6
    -2

# 输出样例 #

26
    
    
    最初想到的解法，是O(n^3)的，即开数组dp[n][m]显然空间爆了，然后数组降到一维，只存目前为止，分1~m段的最大和，以及记录最后一段到哪tag，然后对于dp[k],枚举dp[k] + sum[i] - sum[tag[k]]，以及dp[k - 1] + sum[i] - sum[j](j >= tag[k - 1]),找最大值，并相应的修改tag。时间不少。
    再仔细一想，实际上，就两种情况，即是否加上第i个数。那么实际上，开一个数组dp[m][2]即可，0表示不加第i个数，1表示加。
    第一次代码：

#include <iostream>
    #include <cstdlib>
    #include <cstdio>
    using namespace std;
    typedef long long ll;
    int n,m,d;
    ll dp[5005];
    ll sum[5005];
    int tag[5005];
    int main() {
        while(~scanf("%d%d",&n,&m)) {
            for(int i = 1;i <= n;i ++) {
                scanf("%d",&d);
                sum[i] = sum[i - 1] + d;
                for(int k = m;k >= 1;k --) {
                    if(sum[i] - sum[tag[k]] >= 0) {
                        dp[k] += sum[i] - sum[tag[k]];
                        tag[k] = i;
                    }
                    for(int j = tag[k - 1];j <= i;j ++) {
                        if(dp[k - 1] + sum[i] - sum[j] > dp[k]) {
                            dp[k] = dp[k - 1] + sum[i] - sum[j];
                            tag[k] = i;
                        }
                    }
                }
            }
            printf("%lld\n",dp[m]);
        }
        return 0;
    }

第二次代码：

#include <iostream>
    #include <cstdlib>
    #include <cstdio>
    using namespace std;
    typedef long long ll;
    int n,m,d;
    ll dp[5005][2];
    int main() {
        while(~scanf("%d%d",&n,&m)) {
            for(int i = 1;i <= n;i ++) {
                scanf("%d",&d);
                for(int k = m;k >= 1;k --) {
                    dp[k][0] = max(dp[k][0],dp[k][1]);
                    dp[k][1] = max(dp[k - 1][0],dp[k][1]) + d;
                }
            }
            printf("%lld\n",max(dp[m][0],dp[m][1]));
        }
        return 0;
    }

转载于:https://www.cnblogs.com/8023spz/p/10908835.html