南邮Wishare小Z吃自助餐(dp 最大m子段和)

有一篇讲解最大m子段和的博客,了解知识点再看题 。

代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
const int INF = 1e9;
ll dp[2][maxn];
ll a[maxn];
int n, m;

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i]);
    }

    for(int i = 0; i <= n; i++)
        dp[0][i] = dp[1][i] = 0;

    ll ans = 0;     //可以不选,保证结果 >= 0

    int k = 1;
    for(int i = 1; i <= m; i++, k ^= 1)     //一开始for循环里又定义了一个局部k,没注意,wa了好久...
    {
        ll maxx = -INF;
        dp[k][i - 1] = -INF;
        for(int j = i; j <= n; j++)
        {
            dp[k][j] = max(dp[k][j], dp[k][j-1] + a[j]);    //接在dp[i][j-1]后的情况
            maxx = max(maxx, dp[k^1][j - 1]);
            dp[k][j] = max(dp[k][j], maxx + a[j]);          //接在dp[i - 1][i ~ j - 1]中最大值后面的情况
            ans = max(ans, dp[k][j]);        //此题可以不选任何一段,所以ans每次同步更新            
        }
    }
    cout << ans << endl;
    return 0;
}

 

版权声明:本文为qq_38577732原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_38577732/article/details/89567256