https://codeforces.com/contest/940/problem/E
题目大意
给出 $n \le 10 ^ 5$ 长的数组 $a (1 \le a_i \le 10 ^ 9)$ 和常数 $c \le 10^5$ ，可以将数组分为一些连续的子数组。对于每个子数组，可以将其最小的 $\lfloor \frac{len}{c} \rfloor$ 个元素的权值减去。问剩余权值的和的最小值是多少。
简要题解
重要观察：最终答案里，只需要长为 $c$ 和 $1$ 的子数组。
对于 $len < c$ 的数组，显然我们无法删掉任何权值（$c = 1$ 的情况会被选 $c$ 长的转移吸收，这里先不考虑），因此与选 $len$ 个 $1$ 长的数组没有区别。
对于 $c < len <2c$ 的数组，可以把数组收缩到 $c$ 长且包含最后删去的数，结果不会更差。
对于 $i \ge 2, ic <= len < (i + 1)c$ 的情况，我们会删去 $i$ 个数，考虑直接将区间分为 $i - 1$ 段长度为 $len$ 的，和一段剩下的长度（这一段可以最终按照上一种情况收缩为 $c$ 长），则这样得出的结果不会更差。证明：
-
若按照一大段的选法删掉的数，在每段种刚好一个，则结果一致。
-
若按照一大段的选法删掉的数在某段 $i$ 中有两个或以上，则必定有段没有选，注意我们删的是所有段中最小的一些数，因此剩下的数 $\ge$ 删掉的数，从而我们分段的选法，总会能删掉不小于原先大段删除的数。
至此，我们可以通过动态规划，对于每个位置 $i$ 只需枚举 $1$ 和 $c$ 两种转移即可。因为需要处理 $c$ 长的所有区间最小值，可以使用单调栈。
注意 $c > n$ 时无法减掉任何权值。
复杂度
$T$：$O(n)$
$S$：$O(n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
const LL INF = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n, c; cin >> n >> c;
vector<int> a(n);
for (int& i : a) cin >> i;
vector<LL> sum(n + 1);
for (int i = 0; i < n; i++) {
sum[i + 1] = sum[i] + a[i];
}
if (c > n) {
cout << sum[n] << '\n';
return;
}
vector<int> mi(n - c + 1);
deque<int> qu;
for (int i = 0; i < n; i++) {
if (!qu.empty() && qu.front() <= i - c) qu.pop_front();
while (!qu.empty() && a[qu.back()] >= a[i]) {
qu.pop_back();
}
qu.push_back(i);
if (i - c + 1 >= 0) {
mi[i - c + 1] = a[qu.front()];
}
}
vector<LL> dp(n + 1, INF);
dp[0] = 0;
for (int i = 0; i < n; i++) {
dp[i + 1] = dp[i] + a[i];
if (i - c + 1 >= 0) {
cmin(dp[i + 1], dp[i - c + 1] + (sum[i + 1] - sum[i - c + 1]) - mi[i - c + 1]);
}
}
cout << dp[n] << '\n';
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: D. Alena And The Heater - Codeforces Round 466 (Div. 2)