1010: [HNOI2008]玩具裝箱toy

Time Limit: 1 Sec??Memory Limit: 162 MB
Submit: 2254??Solved: 744
[Submit][Status][Discuss]

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

_________________________________________

1 Program Stone; 2 var i,j,n,l,head,tail:longint; 3 s,f,y,que:array[0..100000]of int64; 4 function delhead(i,j,k:longint):boolean; 5 begin 6 if y[j]-y[k]>(s[j]-s[k])*2*s[i] then exit(true) else exit(false); 7 end; 8 function deltail(i,j,k:longint):boolean; 9 begin 10 if (y[i]-y[j])*(s[j]-s[k])<(y[j]-y[k])*(s[i]-s[j]) then exit(true) else exit(false); 11 end; 12 Begin 13 assign(input,'input.in');reset(input); 14 readln(n,l); 15 for i:=1 to n do 16 begin 17 readln(s[i]); 18 inc(s[i],s[i-1]); 19 end; 20 for i:=1 to n do s[i]:=s[i]+i; 21 head:=0;tail:=0; 22 for i:=1 to n do 23 begin 24 while (tail>head)and(delhead(i,que[head],que[head+1])) do inc(head); 25 j:=que[head]; 26 f[i]:=f[j]+sqr(s[i]-s[j]-l-1); 27 y[i]:=f[i]+sqr(s[i])+2*s[i]*(l+1); 28 while (tail>head)and(deltail(i,que[tail],que[tail-1])) do dec(tail); 29 inc(tail); 30 que[tail]:=i; 31 end; 32 writeln(f[n]); 33 close(input); 34 end. 35 36

?

轉載于:https://www.cnblogs.com/yesphet/p/5236355.html

總結

以上是生活随笔為你收集整理的bzoj 1010: [HNOI2008]玩具装箱toy 2011-12-27的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。