(IOICamp_2016) 30. 序列分割問題

題目備份：

這是一題DP斜率優化的題目！

可以想想看喔！

(題解日後補上)

#include <iostream>
#include <stdio.h>
#include <queue>
#include <cstring>
using namespace std;

typedef long long LL;
const int MAX_K = 106;
const int MAX_N = 1e4 + 6;
const LL INF= 1e17 + 6;

LL dp[MAX_K][MAX_N];
LL pre[MAX_N],s[MAX_N]; //s-->prefix sum, pre--weight prefix sum

int id;

LL f(int i) {
    return pre[i];
}

LL g(int j) {
    return dp[id][j] - pre[j] + s[j]*j;
}

LL h(int j) {
    return -j;
}

LL t(int i) {
    return s[i];
}

struct Line {
    LL m,b;
    LL val(LL x) {
        return m*x+b;
    }
};

Line MP(LL _m,LL _b) {
    return (Line){_m,_b};
}

bool check(Line l1,Line l2,Line l3) {
    return (l2.b-l1.b)*(l1.m-l3.m) <= (l1.m-l2.m)*(l3.b-l1.b);
}

LL a[MAX_N];

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        int n,K;
        scanf("%d %d",&n,&K);
        s[0] = pre[0] = 0;
        for (int i=1;n>=i;i++) {
            scanf("%lld",&a[i]);
            s[i] = s[i-1] + a[i];
            pre[i] = pre[i-1] + i*a[i];
        }
        for (int i=1;n>=i;i++) {
            dp[1][i] = pre[i];
        }
        for (int k=2;K>=k;k++) {
            deque<Line> dq;
            id = k-1;
            dq.push_back(MP(h(k-1),g(k-1)));
            for (int i=k;n>=i;i++) {
                //cout<<"sz = "<<dq.size()<<endl;
                while (dq.size()>1&&dq[0].val(t(i)) > dq[1].val(t(i))) dq.pop_front();
                dp[k][i] = f(i) + dq[0].val(t(i));
                Line newline=MP(h(i),g(i));
                while (dq.size()>1 && check(dq[dq.size()-1],dq[dq.size()-2],newline)) dq.pop_back();
                dq.push_back(newline);
                //cout<<"dp["<<k<<"]["<<i<<"] = "<<dp[k][i]<<endl;
            }
        }
        for (int i=1;K>=i;i++) {
            if (i!=1) printf(" ");
            printf("%lld",dp[i][n]);
        }
        puts("");
    }
}