CF1969C Minimizing the Sum 题解

题目链接：Minimizing the Sum

题意：

给你一个长度为 \(n(1 \le n \le 3 \times 10^5)\) 的整数数组 \(a(1 \le a_i \le 10^9)\)。

你可以执行以下操作：选择数组中的一个元素，并用其邻近元素的值替换它。

你的任务是计算在执行上述操作最多 \(k(0 \le k \le 10)\) 次的情况下，数组的总和可能达到的最小值。

注意到 \(k\) 十分的小，我们可以直接dp

设 \(f_{i,j}\) 表示前 \(i\) 个数修改 \(j\) 次的最小值。转移就钦定 \([l+1,~i]\)​ 全部推成最小值。

时间复杂度 \(\mathcal{O}(nk^2)\)

代码：（考场上光速写的，可能不够优雅）

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(3e5 + 15))

int n, a[N], f[N][12];
void solve()
{
    int k, s = 0; cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 0; i <= n; i++)
        for(int t = 0; t <= k; t++) f[i][t] = INF;
    f[0][0] = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= k; j++)
        {
            down(f[i][j], f[i - 1][j] + a[i]);
            int mn = a[i];
            for(int l = 1; j - l + 1 >= 0 && i - l >= 0; l++)
            {
                down(mn, a[i - l + 1]);
                down(f[i][j], f[i - l][j - l + 1] + mn * l);
            }
        }
    }
    int res = INF;
    for(int i = 0; i <= k; i++) down(res, f[n][i]);
    cout << res << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}