[HNOI2008]玩具裝箱TOY

洛谷題目連接:[HNOI2008]玩具裝箱TOY

題目描述

P教授要去看奧運，但是他舍不下他的玩具，于是他決定把所有的玩具運到北京。他使用自己的壓縮器進行壓縮，其可以將任意物品變成一堆，再放到一種特殊的一維容器中。P教授有編號為1...N的N件玩具，第i件玩具經過壓縮后變成一維長度為Ci.為了方便整理，P教授要求在一個一維容器中的玩具編號是連續的。同時如果一個一維容器中有多個玩具，那么兩件玩具之間要加入一個單位長度的填充物，形式地說如果將第i件玩具到第j個玩具放到一個容器中，那么容器的長度將為 x=j-i+Sigma(Ck) i<=K<=j 制作容器的費用與容器的長度有關，根據教授研究，如果容器長度為x,其制作費用為(X-L)^2.其中L是一個常量。P教授不關心容器的數目，他可以制作出任意長度的容器，甚至超過L。但他希望費用最小.

輸入輸出格式

輸入格式：

第一行輸入兩個整數N，L.接下來N行輸入Ci.1<=N<=50000,1<=L,Ci<=10^7

輸出格式：

輸出最小費用

輸入輸出樣例

輸入樣例#1：

5 4
3
4
2
1
4

輸出樣例#1：

1

一句話題意: 給出\(n\)個玩具,你可以將一些連續的玩具放到同一個箱子內,這樣的費用是\(x=j-i+\displaystyle{\sum^{j}_{k=i}} C_k\),問要裝這\(n\)個玩具所需要的最小費用.

題解: DP方程應該很顯然,我們定義\(f[i]\)表示裝到第\(i\)個玩具所需要的最小費用.那么則有\(f[i]=min(f[j]+(sum[i]+i-sum[j]-j-L-1)^2\),其中\((j<i)\).按照慣例,我們還是先對這個式子進行化簡,為了簡便計算,這里用\(a[i]\)表示\(sum[i]+i\), 用\(b[i]\)表示\(sum[i]+i+L+1\),設\(j\)狀態為轉移到\(i\)狀態的最優情況,則有:\[f[i]=f[j]+(a[i]-b[i])^2\]
展開得:\[f[i]=f[j]+a[i]^2-2*a[i]*b[j]+b[j]^2\]
將所有只含有\(i\)的以及含有\(i,j\)兩項乘積的都放到左邊:\[2*a[i]*b[j]+f[i]-a[i]^2=f[j]+b[j]^2\]
可以將\(b[j]\)看做直線的自變量\(x\),將\(2*a[i]\)看做直線的斜率\(k\),將\(f[j]+b[j]^2\)看做直線的\(y\),接下來一波斜率優化的套路就可以了.

#include<bits/stdc++.h>
using namespace std;
const int N=50000+5;
typedef long long lol;lol n, l, h, t, q[N], f[N], c[N], s[N];inline lol a(lol i){return i+s[i]-1-l;}
inline lol b(lol i){return i+s[i];}
inline lol x(lol i){return b(i);}
inline lol y(lol i){return f[i]+b(i)*b(i);}
inline double slope(lol i, lol j){return (double) (y(i)-y(j))/(x(i)-x(j));}int main(){ios::sync_with_stdio(false);cin >> n >> l;for(int i=1;i<=n;i++)cin >> c[i], s[i] = s[i-1]+c[i];h = 0, t = 0, q[h] = 0; f[0] = 0;for(int i=1;i<=n;i++){while(h < t && slope(q[h], q[h+1]) <= 2*a(i)) h++;f[i] = y(q[h])-2*a(i)*b(q[h])+a(i)*a(i);while(h < t && slope(q[t], q[t-1]) > slope(q[t], i)) t--;q[++t] = i;}cout << f[n] << endl;return 0;
}