[CF1155D] Beautiful Array

[CF1155D] Beautiful Array - dp

Description

定义一个序列的美丽程度为其所有子串的和的最大值（子串可以是空的），给了你一次操作的机会，你需要选择序列的一个子串，将其中所有数乘上给定的一个常数 x，求这个序列最大的美丽程度。

Solution

设 (f[i][0/1/2]) 表示到达 i 为止的最大子段和（还没有开始用 x，正在用 x，已经不再用 x）

#include <bits/stdc++.h>
using namespace std;

#define int long long 

const int N = 1e6 + 5;
int n, x, a[N], f[N][3];

signed main()
{
    ios::sync_with_stdio(false);
    cin >> n >> x;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    int ans = 0;

    for (int i = 1; i <= n; i++)
    {
        f[i][0] = max(f[i - 1][0] + a[i], a[i]);
        f[i][1] = max(max(f[i - 1][0], f[i - 1][1]) + x * a[i], x * a[i]);
        f[i][2] = max(max(f[i - 1][1], f[i - 1][2]) + a[i], a[i]);
        ans = max(ans, f[i][0]);
        ans = max(ans, f[i][1]);
        ans = max(ans, f[i][2]);
    }

    cout << ans << endl;
}