C题

Problem - C - Codeforces

上课的时候刘神看了眼这个题，作为cj的我来替他ac

题意：

给出n个数，然后找到一个子串，每个数加上x，使子串的和最大，子串可以为空，然后依次输出0~n+1的最优和

思路：

首先找到0~n长度的最大子串和，然后确定每个长度的最优解（因为当当前长度为7时，最优解可能是来自1的），最后按情况加上x（如果最优解来自比它小的长度，则加上比它小的长度个，反之加上它的长度个）

#include <bits/stdc++.h>

using namespace std;

const int N = 5050;
const int INF = 0x3f3f3f3f;

int a[N];
int d[N];
int f[N];

void solve()
{
    int n, x;
    cin >> n >> x;
    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        d[i] = d[i - 1] + a[i];
    }

    memset(f, -INF, sizeof f);
    for (int i = 1; i <= n; i ++)
    {
        for (int j = i; j <= n; j ++)
        {
            int len = j - i + 1;
            f[len] = max(f[len], d[j] - d[i - 1]);
        }
    }

    f[0] = 0;
    for (int i = 0; i <= n; i ++)
    {
        int res = 0;
        for (int j = 0; j <= n; j ++)
        {
            if (i > j)
                res = max(res, f[j] + j * x);
            else
                res = max(res, f[j] + i * x);
        }
        cout << res << ' ';
    }
    cout << endl;
}

int main()
{
    int t;
    cin >> t;
    while (t --)
    {
        solve();
    }
}