題目描述

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

感謝@ACの666 提供的Latex題面

輸入輸出格式

輸入格式：

?

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

?

輸出格式：

?

輸出最小費(fèi)用

?

輸入輸出樣例

輸入樣例#1：?復(fù)制 5 4 3 4 2 1 4 輸出樣例#1：?復(fù)制 1

---

---

---

---

---

---

---

---

---

1 #include "bits/stdc++.h" 2 3 using namespace std; 4 typedef long long ll; 5 6 ll s[600000],f[600000],q[600000]; 7 ll n,m; 8 9 ll y(ll x) 10 { 11 return x+s[x]; 12 } 13 14 ll slope(ll j, ll k) 15 { 16 //return f[j]+(ll)(pow(y(j)+1+m,2)) - (f[k]+(ll)pow(y(k)+1+m,2) ); 17 return f[j]+(ll)pow(y(j),2)+2*(1+m)*y(j) - (f[k]+(ll)pow(y(k),2)+2*(1+m)*y(k) ) ; 18 19 } 20 ll down(ll j,ll k) 21 { 22 return (2*y(j)-2*y(k)); 23 } 24 25 26 27 int main() 28 { 29 while (cin>>n>>m) 30 { 31 for (int i=1;i<=n;i++) 32 { 33 ll x;cin>>x;s[i]=s[i-1]+x; 34 } 35 int L=1,R=1; 36 q[1]=f[0]=0; 37 for (int i=1;i<=n;i++) 38 { 39 while (L<R&&slope(q[L+1],q[L])<=y(i)*down(q[L+1],q[L]))L++; 40 41 int t=q[L]; 42 43 /*f[i]=f[t]+(ll)(pow(y(t),2))+1LL*2*(1+m)*y(t)\ 44 -1ll*2*y(t)*y(i)+(ll)pow(y(i),2)-1ll*2*(1+m)*y(i)+1LL*(1+m)*(1+m); 45 */ // 這么寫就wa了，不知道為什么 46 47 f[i]=f[t]+(ll)pow(y(i)-y(t)-1-m,2); 48 49 50 while(L<R&&slope(q[R],q[R-1])*down(i,q[R])>=down(q[R],q[R-1])*slope(i,q[R]))R--; 51 52 q[++R]=i; 53 } 54 cout<<f[n]<<endl; 55 } 56 57 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/zhangbuang/p/10616266.html

總結(jié)

以上是生活随笔為你收集整理的P3195 [HNOI2008]玩具装箱TOY(斜率优化）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。