[APIO2014]序列分割 --- 斜率优化DP

#include
#include#define sid 100050
#define dd double
#define ll long long
#define ri register int
using namespace std;

#define getchar() *S ++
char RR[30000005], *S = RR;
inline int read(){
    int p = 0, w = 1;
    char c = getchar();
    while(c > ‘9‘ || c ‘0‘) {
        if(c == ‘-‘) w = -1;
        c =  getchar();
    }
    while(c >= ‘0‘ && c ‘9‘) {
        p = p * 10 + c - ‘0‘;
        c = getchar();
    }
    return p * w;
}

ll sum[sid], dp[2][sid];
int lst[205][sid], q[sid], n, k;
bool now = 0, pre = 1;

#define x(g) sum[(g)]
#define y(g) (sum[(g)]*sum[(g)]-dp[pre][(g)])
inline dd s(int i, int j) {
    if(x(i) == x(j)) return -1e18;
    return (dd)(y(i) - y(j)) / (dd)(x(i) - x(j));
}

int main() {
    fread(RR, 1, sizeof(RR), stdin);
    n = read(); k = read();
    for(ri i = 1; i 1] + read();
    for(ri j = 1; j ) {
        int fr = 1, to = 1; now ^= 1; pre ^= 1;
        for(ri i = 1; i ) {
            while(fr + 1 1]) ;
            dp[now][i] = dp[pre][q[fr]] + sum[q[fr]] * (sum[i] - sum[q[fr]]);
            lst[j][i]=q[fr];
            while(fr + 1 1], q[to]) >= s(q[to], i)) to --;
            q[++ to] = i;
        }
    }
    printf("%lld\n",dp[now][n]);
    int e = n;
    for(ri i = k; i >= 1; i --) {
        e = lst[i][e]; printf("%d ", e);
    }
    return 0;
}