(IOICamp_Judge) 91.列印機問題 [1D/1D Convex DP優化，1D/1D Monge Condition]

https://judge.ioicamp.org/problems/91

因為怕題目之後不見，做個備份：

列印機問題

Time Limit: 1s

Description

你正在修機器學習的課程，因為作業太困難了，所以你決定把題目印下來慢慢研究。

現在有一台計費方式很奇怪的列印機，當你送出一份要列印的文件時，列印機會對文件中的每一頁算出列印該頁所需的成本，令該份文件每一頁的列印成本總和為 x，列印這份文件所需的價錢就是 x3+K（K 為給定的常數）。

為了省錢，你決定把整份作業拆成好幾份文件列印，但是列印完還要自己重新排列很麻煩，因此你決定每次送出去列印的文件都必須是在原始作業檔案中頁數連續的一段，例如第 2 頁到第 5頁。

整份作業總共有 N 頁，並順利算出每一頁的列印成本。現在你要經過數次如上的列印，確保自己拿到作業中每一頁的紙本（同一頁可以被列印多次），請問你所需花費的錢最少為多少？

Input Format

第一行有一個正整數 T，代表總共有幾筆測試資料。

每筆測試資料包含兩行，其中的第一行為兩個正整數 N,K，表示機器學習作業的頁數以及列印機計價方式中的常數 K。第二行包含 N 個整數，依序代表作業中第 1 頁列印成本、第 2頁列印成本、第 3 頁列印成本………第 N 頁列印成本。

• 1≤T≤100
• 1≤N≤105
• 1≤K≤1012
• 0≤每一頁的列印成本 ≤10
• 所有測試資料中的 N 加總不超過 106

Output Format

對於每筆測試資料，請輸出一行一個整數，代表用最佳方式列印所需花費的最少金額。

Sample Input

2
3 5
2 4 1
5 514
3 8 2 0 1

Sample Output

88
2108

Hint

在第一筆範例測試資料中，最佳方法是分別送出只包含第 1 頁的文件、只包含第 2 頁的文件、只包含第 3$3$ 頁的文件，共 3$3$ 份文件去列印，於是總花費的金額會是 (23+5)+(43+5)+(13+5)=88

在第二筆範例測試資料中，最佳方法是分別送出只包含第 1 頁的文件、只包含第 2 頁的文件、包含第 3$3$ 頁到第 5$5$ 頁的文件，共 3$3$ 份文件去列印，於是總花費的金額會是 (33+514)+(83+514)+((2+0+1)3+514)=2108

這題主要是用Convex 1D/1D DP優化

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

typedef pair<int,int> pii;
typedef pair<int,pii> piii;
typedef long long LL;
const int MAX_N = 1e5 + 6;

LL a[MAX_N],s[MAX_N],k;
LL dp[MAX_N];

LL f(LL i,LL j) {
    return dp[i]+ ( k+(s[j]-s[i])*(s[j]-s[i])*(s[j]-s[i]) );
}

struct Seg {
    LL i,l,r;
};

Seg MP(int _i,int _l,int _r) {
    return (Seg){_i,_l,_r};
}

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        int n;
        scanf("%d %lld",&n,&k);
        memset(s,0,sizeof(s));
        int m=1;
        for (int i=1;n>=i;i++) {
            scanf("%lld",&a[i]);
            if (a[i] == 0) {
                continue;
            }
            s[m] = s[m-1]+a[i];
            m++;
        }
        m--;
        memset(dp,0,sizeof(dp));
        dp[0]=0;
        deque<Seg> dq;
        dq.push_back(MP(0,1,m));
        for (int j=1;m>=j;j++) {
            while (dq.size()) {
                Seg tmp=dq.back();
                if (f(tmp.i,tmp.l) > f(j-1,tmp.l)) dq.pop_back();
                else break;
            }
            if (dq.size()) {
                Seg tmp=dq.back();
                int L=tmp.l,R=tmp.r+1;
                while (R-L>1) {
                    int mid=(L+R)>>1;
                    if (f(tmp.i,mid) > f(j-1,mid)) R=mid;
                    else L=mid;
                }
                dq.pop_back();
                dq.push_back(MP(tmp.i,tmp.l,L));
                if (L!=m) dq.push_back(MP(j-1,L+1,m));
                dp[j] = f(dq[0].i,j);
                if (dq[0].r==j) dq.pop_front();
                else {
                    Seg temp=dq.front();
                    dq.pop_front();
                    Seg ret=MP(temp.i,temp.l+1,temp.r);
                    dq.push_front(ret);
                }
            }
            else {
                dq.push_back(MP(j-1,j+1,n));
                dp[j] = f(j-1,j);
            }
        }
        if (m!=0)printf("%lld\n",dp[m]);
        else printf("%lld\n",k);
    }
}