AcWing 334. K匿名序列

2021-03-17 20:23

阅读：572

标签：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

上一篇：webstrom Debug 调试vue项目

下一篇：Z390上安装Win10与Win7

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：AcWing 334. K匿名序列
文章链接：http://soscw.com/index.php/essay/65450.html

亲，登录后才可以留言！

AcWing 334. K匿名序列

评论

热门文章

推荐文章

最新文章

置顶文章