luoguP3648 [APIO2014]序列分割

https://www.luogu.org/problemnew/show/P3648

同bzoj3675

这题斜率优化+滚动数组就可以了qwq

因为我是在飞机上瞎bb的式子，所以可能会和别的题解的式子不一样(反正 A 题了对吧)

推的过程什么的都写在最底下的注释里了，大家可以选择先查看最底下的过程(您是神犇可以不用看这篇博客)

但这篇题解不知为什么在bzoj上过不了，请dalao们赐教

#include <bits/stdc++.h>

using namespace std;

template <typename T>

inline void read(T &f) {

    f = 0; T fu = 1; char c = getchar();

    while (c < '0' || c > '9') {if (c == '-') fu = -1; c = getchar();}

    while (c >= '0' && c <= '9') {f = (f << 3) + (f << 1) + (c & 15); c = getchar();}

    f *= fu;

}

typedef long long ll;

const int N = 100000 + 10;

const int M = 200 + 10;

ll f[2][N], s[N], a[N];

int fr[M][N], q[N], ans[N], head, tail;

int n, m;

bool pd(int a, int b, int c, int d) {

    // g(b, c) >= s[n] - s[d]

    // (f[b] - f[c]) / (s[b] - s[c]) >= s[n] - s[d]

    if(f[a][b] - f[a][c] <= (s[b] - s[c]) * (s[n] - s[d])) return 1;

    return 0;

}

bool pd2(int a, int b, int c, int d) {

    // g(b, c) < g(c, d)

    // (f[b] - f[c]) / (s[b] - s[c]) < (f[c] - f[d]) / (s[c] - s[d])

    // (f[b] - f[c]) * (s[c] - s[d]) < (f[c] - f[d]) * (s[b] - s[c])

    if((f[a][b] - f[a][c]) * (s[c] - s[d]) < (f[a][c] - f[a][d]) * (s[b] - s[c])) return 1;

    return 0;

}

int main() {

    read(n); read(m);

    for(int i = 1; i <= n; i++) {

        read(a[i]);

        s[i] = s[i - 1] + a[i];

    }

    for(int i = 1; i <= m; i++) {

        head = 0, tail = 0; q[0] = i - 1;

        for(int j = i; j <= n; j++) {

            // 保证队列里有两个元素

            while(head + 1 <= tail) {

                if(pd((i & 1) ^ 1, q[head], q[head + 1], j)) head++;

                else break;

            }

            f[i & 1][j] = f[(i & 1) ^ 1][q[head]] + (s[n] - s[j]) * (s[j] - s[q[head]]);

            fr[i][j] = q[head];

            while(head + 1 <= tail) {

                if(pd2((i & 1) ^ 1, q[tail - 1], q[tail], j)) tail--;

                else break;

            }

            q[++tail] = j;

        }

    }

    ll maxn = -1; int num;

    for(int i = n; i >= m; i--) if(f[m & 1][i] > maxn) maxn = f[m & 1][i], num = i;

    printf("%lld\n", maxn);

    for(int i = m; i >= 1; i--) {

        ans[i] = num;

        num = fr[i][num];

    }

    for(int i = 1; i < m; i++) printf("%d ", ans[i]);

    printf("%d\n", ans[m]);

    return 0;

}

// f[i] 表示取到了第 i 个数获得的最大价值

// f[i] = f[j] + (s[n] - s[i]) * (s[i] - s[j])

// f[i] = f[j] + s[n] * s[i] - s[n] * s[j] - s[i] * s[i] + s[i] * s[j]

// 假设 j 比 k 优, j < k

// f[j] + s[n] * s[i] - s[n] * s[j] - s[i] * s[i] + s[i] * s[j] > f[k] + s[n] * s[i] - s[n] * s[k] - s[i] * s[i] + s[i] * s[k]

// f[j] - s[n] * s[j] + s[i] * s[j] > f[k] - s[n] * s[k] + s[i] * s[k]

// f[j] - s[j] * (s[n] - s[i]) > f[k] - s[k] * (s[n] - s[i])

// f[j] - f[k] > (s[j] - s[k]) * (s[n] - s[i])

// (f[j] - f[k]) / (s[j] - s[k]) < s[n] - s[i]

// 令 g(i, j) 表示 i 和 j 的斜率

// i < j < k

// if g(i, j) < g(j, k)

//   if g(i, j) < s[n] - s[x]  j 比 i 差

//   if g(i, j) >= s[n] - s[x]  i 比 j 差, j 比 k 差

// 所以 j 就被扔掉了 QAQ

// 令 a, b 为队首两点

// if g(a, b) >= s[n] - s[i]

// a 比 b 差

// 当 i 上升时, s[n] - s[i] 单调不增

// a 永远比 b 差

// 飞机上没有博客只能自己推式子好痛苦啊 QAQ

巴特西

luoguP3648 [APIO2014]序列分割

最新文章

热门文章