AcWing 334. K匿名序列
2021-03-17 20:23
阅读：650
标签：return problem iostream stream line turn 匿名 最小 ons
大型补档计划
题目链接
就是把序列分成无数段，每段长度 $ >= K$，然后 \([l, r]\) 这段的花费是 \(S[r] - S[l - 1] - (r - l + 1) * a[l]\) （把所有数减成 \(a[l]\)）
很容易列出状态转移方程：
设 \(f[i]\) 为前 i 个分完段的最小花费
\(f[i] = f[j] + s[i] - s[j] - (i - j) * a[j + 1]\)
移项：
\(\underline{f[j] - s[j] + j * a[j + 1]}_y = \underline{i}_k * \underline{a[j + 1]}_x - \underline{s[i] + f[i]}_b\)
一个鲜明的斜率优化，其中斜率、横坐标都是递增的，用弹出法即可。
#include
#include
#include
using namespace std;
typedef long long LL;
const int N = 500005;
const LL INF = 0x3f3f3f3f3f3f3f3f;
int n, K, a[N], q[N];
LL f[N], s[N];
LL inline y(int i) { return f[i] - s[i] + i * (LL)a[i + 1]; }
LL inline x(int i) { return a[i + 1]; }
int main() {
int T; scanf("%d", &T);
while (T--) {
memset(f, 0x3f, sizeof f);
scanf("%d%d", &n, &K);
for (int i = 1; i = K) {
while (hh = (y(i - K) - y(q[tt])) * (x(q[tt]) - x(q[tt - 1]))) tt--;
q[++tt] = i - K;
}
while (hh AcWing 334. K匿名序列
标签：return problem iostream stream line turn 匿名 最小 ons
原文地址：https://www.cnblogs.com/dmoransky/p/12380602.html
评论
亲，登录后才可以留言！