题意
Codeforces Round 809 (Div. 2) D1. Chopping Carrots (Easy Version)
给你两个整数\(n(1 \le n \le 3e5), k(0\le k \le 10)\), 一个数组 \(a(1 \le a_i \le 10^9)\)。你可以进行如下操作最多 \(k\) 次：选定一个数 \(i(1 \le i \le n)\)，让其变为相邻的数(变为\(a_{i-1}, a_{i+1}\)中的一个），\(a_1\) 与 \(a_n\) 不相邻。
输出数组各个元素之和最小值。
思路
这道题观察数据范围可以猜测解法可能与 \(k\) 有关，复杂度可能为 \(O(nk), O(nk^2)\) 甚至 \(O(nk^3)\) 。
打假一下贪心做法，就是时刻维护相邻元素的差，每次操作都选取最大的差来操作。
例如如下数据：
4 2
120 70 1 80
如果按照贪心思路，最后数组变为了120 1 1 1，但正确结果的数组应该是1 1 1 80。
这道题需要提取出如下的性质：
- 如果一段区间被操作了，那么最终的数组一定是这个区间中的最小值
- 操作的区间与区间之间不会有交叉部分
这里就要用到dp来解决(一般我的各种算法都不行，贪心也被hack时候，就会考虑dp)。
设定 \(f_{i,j}\) 表示前 \(i\) 个元素中，用了 \(j\) 次操作后的元素之和的最小值。
根据定义，表示出状态转移： \(f_{i,j} = min\{f_{i-1,j} + minv * 1, f_{i-2,j-1} + minv * 2, ..., f_{i-(k+1),j-k} + minv * (k+1) \}\)。其中 \(minv\) 表示 \([i-d-1,i]\) 区间中的最小值
代码
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#define fi first
#define se second
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ull P = 131;
const double eps = 1e-4;
const int N = 3e5+10, M = 11;
ll n, k, a[N];
ll f[N][M];
void solve() {
scanf("%lld%lld", &n, &k);
for (int i=1; i<=n; i++)
scanf("%lld", &a[i]);
for (int i=0; i<=n; i++)
for (int j=0; j<=k+1; j++)
f[i][j] = inf;
f[0][0] = 0;
for (int i=1; i<=n; i++) {
for (int j=0; j<=k; j++) {
ll minv = a[i];
for (int d=0; d<=j && i-d-1>=0; d++) {
minv = min(minv, a[i-d]);
f[i][j] = min(f[i][j], f[i-d-1][j-d] + minv * (d + 1));
}
}
}
ll res = inf;
for (int i=0; i<=k; i++) res = min(res, f[n][i]);
printf("%lld\n", res);
}
int main() {
// multiple case
int t; scanf("%d", &t);
while(t--) {
solve();
}
// single case
// solve();
return 0;
}