题解 P3648 【[APIO2014]序列分割】

· · 题解

\Large \texttt{My Blog}

引理：

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

证明：若分了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;
}