CF1644C-Increase Subarray Sums

2022-05-01 题解

题目大意：给定一个长度为n的数列。一次操作可以在整个数列中任意选择k个元素，每个元素的值加上x。问当k=0,1,2,…n时，进行一次操作之后，数列中和最大的子段（可以为空）的和为多少。

由于x非负，不论取哪个子段，都希望它里面的元素能尽可能全部加上x。数列很小，可以轻松求出任意长度和最大的子段。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll a[100005], s[100005], dp[100005];
int main()
{
    ll n, x, res;
    int _, i, j, t;
    scanf("%d", &_);
    while (_--)
    {
        scanf("%lld%lld", &n, &x);
        for (i = 1; i <= n; i++)
        {
            scanf("%lld", &a[i]);
            s[i] = s[i - 1] + a[i];
        }
        for (i = 1; i <= n; i++)
        {
            dp[i] = -1e18;
            for (j = i; j <= n; j++)
                dp[i] = max(dp[i], s[j] - s[j - i]);
        }
        for (i = 0; i <= n; i++)
        {
            for (j = 1, res = 0; j <= n; j++)
                res = max(res, dp[j] + x * min(i, j));
            printf("%lld ", res);
        }
        printf("\n");
    }
    return 0;
}