1010: [HNOI2008]玩具裝箱toy

Time Limit:?1 Sec??Memory Limit:?162 MB

Description

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。但他希望費用最小.

Input

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

Output

輸出最小費用

Sample Input

5 4
3
4
2
1
4

Sample Output

1 動態規劃，先用前綴和s[i]數組 然后dp[i]=min{dp[j]+(i-j-1+s[i]-s[j]-m)^2}(0<=j<i) 斜率優化處理一下。 #include <iostream> #include <string.h> #include <stdio.h> #include <cmath> #include <algorithm> using namespace std; #define N 50500 int n,m,b[N],le,ri; long long s[N],dp[N]; inline long long sqr(long long x){return x*x;} inline double g(int j,int k){return (dp[j]-dp[k]*1.0)/(s[j]-s[k]*1.0)+s[j]+s[k]+2+2*m;} int main(){int i,j,k,l,q,w,e;scanf("%d%d",&n,&m);memset(b,0,sizeof(b));memset(s,0,sizeof(s));memset(dp,0,sizeof(dp));for (i=1;i<=n;i++){scanf("%d",&k);s[i]=s[i-1]+k;}for (i=1;i<=n;i++)s[i]+=i;le=0;ri=0;for (i=1;i<=n;i++){while (ri>le&&g(b[le+1],b[le])<s[i]*2)le++;j=b[le];dp[i]=dp[j]+sqr(s[i]-s[j]-1-m);ri++;b[ri]=i;while (ri>le+1&&g(b[ri],b[ri-1])<g(b[ri-1],b[ri-2])){b[ri-1]=b[ri];ri--;}}cout <<dp[n]<<endl;return 0;}

?

轉載于:https://www.cnblogs.com/HJWJBSR/p/4168070.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

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

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