「Bzoj 3675」「Apio2014」序列分割 (斜率优化DP)

BZOJ 3675
题意：你正在玩一个关于长度为 $n$ 的非负整数序列 $a_i$ 的游戏。这个游戏中你需要把序列分成 $k+1$ 个非空的块。为了得到 $k+1$ 块，你需要重复下面的操作 $k$ 次：
选择一个有超过一个元素的块（初始时你只有一块，即整个序列）
选择两个相邻元素把这个块从中间分开，得到两个非空的块。
每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。

引理：

最终答案和分割顺序无关。

证明：若分了$3$块，设为$a_1,a_2,a_3$
则
$$
a_1 a_2 + (a_1+a_2)a_3 = a_2 a_3 + (a_2 + a_3)a_1
$$
所以两者等价，并且容易扩展到更多块的情况。并且答案是$a$两两相乘的和(或者是$a_1 + (a_1+a_2)a_3 + (a_1+a_2+a_3)a_4 +\dots + (a_1+a_2+ \dots + a_{k-1})a_k$)

那么设$dp(k,i)$为前$i$个分了$k$次的最大值。根据上面的式子，可以有DP方程
$$
dp(k,i)=\max(dp(k-1, j)+s(j) \cdot (s(i) - s(j)))
$$
其中$s(i)$为前缀和。
显然可以斜率优化。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const LL MAXN = 100000 + 5;

    LL n, K, a[MAXN], s[MAXN], dp[205][MAXN], pre[205][MAXN];
    LL q[MAXN], l, r;
    vector<LL > vec;

    LL getx(LL j) {return s[j];}
    LL gety(LL j, LL k) {return dp[k - 1][j] - s[j] * s[j];}
    db getsl(LL a, LL b, LL k) {
        if (getx(a) == getx(b)) return -1e18;
        return 1.0 * (gety(a, k) - gety(b, k)) / (getx(a) - getx(b));
    }

    void clean() {
        ms(pre, 0), ms(s, 0), ms(dp, 0);
    }
    int solve() {

        clean();
        cin >> n >> K;

        for (LL i = 1; i <= n; ++i) scanf("%lld", &a[i]), s[i] = a[i] + s[i - 1];

        for (LL k = 1; k <= K; ++k) {
            l = 1, r = 1, q[1] = 0;
            for (LL i = 1; i <= n; ++i) {
                while (l < r && getsl(q[l], q[l + 1], k) >= -s[i]) ++l;
                dp[k][i] = dp[k - 1][q[l]] + s[q[l]] * (s[i] - s[q[l]]);
                pre[k][i] = q[l];
                while (l < r && getsl(q[r - 1], q[r], k) <= getsl(q[r], i, k)) --r;
                q[++r] = i;
            }
        }

        printf("%lld\n", dp[K][n]);
        LL cur = n, tms = K;
        while (cur != 0) {
            vec.push_back(cur);
            cur = pre[tms][cur], --tms;
        }
        sort(vec.begin(), vec.end());
        for (LL i = 0; i < (LL)vec.size() - 1; ++i) printf("%lld ", vec[i]);

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}