[APIO2014]序列分割

可以直接看一下式子： \[ f(i,k)=\min_{j=1}^{i=1}\{f(j,k-1)+s_j(s_i-s_j)\} \] 因为这个只与上一维的状态有关，所以是可以滚掉一维的，那么令上一维的状态为\(g\)，这一维的状态就为\(f\)

考虑此时的最优决策点\((j<k)\)： \[ \begin{aligned} g(j)+s_j(s_i-s_j)&> g(k)+s_k(s_i-s_k)\\ g(j)+s_js_i-{s_j}^2&> g(k)+s_ks_i-{s_k}^2\\ (g(j)-{s_j}^2)-(g(k)-{s_k}^2)&> s_i(s_k-s_j)\\ \frac {(g(j)-{s_j}^2)-(g(k)-{s_k}^2)}{s_k-s_j}&> s_i \end{aligned} \] 然后注意到，这个\(s_i\)一定是单调递增的，所以可以直接用队列维护斜率单增

然后就写完了

Code

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) {
        x = (x << 1) + (x << 3) + (o ^ 48);
    }
    return x * t;
}

ll s[maxn], f[2][maxn];
int __pre[maxn][205], q[maxn];

inline double Slope(int x, int y, int t)
{
    ll y1 = f[t][x] - s[x] * s[x], x1 = s[x];
    ll y2 = f[t][y] - s[y] * s[y], x2 = s[y];
    if (x1 == x2) return 0;
    return double (y1 - y2) / (x2 - x1);
}

int main()
{
    int n = __read(), k = __read();
    for (int i = 1; i <= n; ++i)
        s[i] = s[i - 1] + __read();

    for (int j = 1; j <= k; ++j) {
        int l(1), r(1), t(j & 1);
        q[1] = 0;
        for (int i = 1; i <= n; ++i) {
            while (l < r && Slope(q[l], q[l + 1], t ^ 1) <= s[i]) ++l;
            __pre[i][j] = q[l];
            f[t][i] = f[t ^ 1][q[l]] + s[q[l]] * (s[i] - s[q[l]]);
            while (l < r && Slope(q[r - 1], q[r], t ^ 1) >= Slope(q[r], i, t ^ 1)) --r;
            q[++r] = i;
        }
    }

    printf ("%lld\n", f[k & 1][n]);
    for (int p = n; k; --k) p = __pre[p][k], printf ("%d ", p);
    puts("");
}