約翰開車回家，又準備順路買點飼料了（咦？為啥要說“又”字？）回家的路程一共有 E 公里，
這一路上會經過 K 家商店，第 i 家店里有 Fi 噸飼料，售價為每噸 Ci 元。約翰打算買 N 噸飼料，他
知道商家的庫存是足夠的，至少所有店的庫存總和不會少于 N。除了購買飼料要錢，運送飼料也是
要花油錢的，約翰的卡車上如果裝著 X 噸飼料，那么他行駛一公里會花掉 X 2 元，行駛 D 公里需要
D X 2 元。已知第 i 家店距約翰所在的起點有 Xi 公里，那么約翰在哪些商店買飼料運回家，才能做到
最省錢呢？

輸入格式
? 第一行：三個整數 K， E 和 N， 1 ≤ K ≤ 10000 , 1 ≤ E ≤ 500 , 1 ≤ N ≤ 500
? 第二行到第 N + 1 行：第 i + 1 行有三個整數 Xi， Fi 和 Ci， 0 < Xi < E, 1 ≤ Fi ≤ 10000, 1 ≤
Ci ≤ 107

輸出格式
? 單個整數：表示購買及運送飼料的最小費用

樣例輸入
2 5 3
3 1 2
4 1 2
1 1 1

樣例輸出
9

解釋
在離家較近的兩家商店里各購買一噸飼料，
則花在路上的錢是 1 + 4 = 5，花在店里的錢是
2 + 2 = 4

?

【分析】

　　嗯，啊，還是好笨，想了挺久。

　　先列DP，f[i][x]=min(f[j][k]+(x-k)^2*(d[i]-d[j])+(x-k)*c[i]) d[i][x]表示走到i，一共買了x個東西的最小費用。

　　但是這樣列的話很難降維，因為答案跟d[j]有關，所以可以用 計算未來費用的思想,就是買的時候直接算他運到終點了。

　　f[i][x]=min(f[j][k]+(x-k)*c[i]+(x^2-k^2)*(s-d[i])) 這樣就可以降維了。

　　f[x]=min(f[k]+(x-k)*c[i]+(x^2-k^2)*(s-d[i])) i直接for，不過要注意一點是要用的是i之前算出的f而不能是i時計算出的f

　　如果沒有限制的話，這樣的方程當然存一個最優解就好了，但是有限制，就要看限制的單調性，我們要x-k<=sm[i] 即 k>=x-sm[i]

　　x按順序枚舉的話就有單調性了。

　　啊，又是一道限制為主的單調隊列ORZ、、、

　　

代碼如下：

1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 #include<queue> 7 #include<cmath> 8 using namespace std; 9 #define Maxn 510 10 #define Maxm 200010 11 #define LL long long 12 13 struct node 14 { 15 LL d,sm,w; 16 }t[Maxn]; 17 18 LL mymin(LL x,LL y) {return x<y?x:y;} 19 LL mymax(LL x,LL y) {return x>y?x:y;} 20 21 bool cmp(node x,node y) {return x.d<y.d;} 22 23 LL q[Maxm],st[Maxm],f[Maxm]; 24 25 int main() 26 { 27 LL v,s,n; 28 scanf("%lld%lld%lld",&v,&s,&n); 29 for(LL i=1;i<=n;i++) scanf("%lld%lld%lld",&t[i].d,&t[i].sm,&t[i].w); 30 sort(t+1,t+1+n,cmp); 31 for(LL i=1;i<=n;i++) t[i].d=s-t[i].d; 32 memset(f,127,sizeof(f)); 33 f[0]=0; 34 int ql,qr; 35 for(LL i=1;i<=n;i++) 36 { 37 ql=qr=1;q[qr]=0;st[qr]=0; 38 for(LL j=1;j<=v;j++) 39 { 40 while(ql<qr&&(j-st[ql])>t[i].sm) ql++; 41 LL now=f[j]; 42 f[j]=mymin(f[j],q[ql]+t[i].d*j*j+t[i].w*j); 43 while(now-j*j*t[i].d-t[i].w*j<=q[qr]&&qr>=ql) qr--; 44 q[++qr]=now-j*j*t[i].d-t[i].w*j;st[qr]=j; 45 } 46 } 47 printf("%lld\n",f[v]); 48 return 0; 49 } View Code

?

?

2016-10-20?09:14:21

?

轉載于:https://www.cnblogs.com/Konjakmoyu/p/5979490.html

總結

以上是生活随笔為你收集整理的Buying Feed, 2010 Nov (单调队列优化DP)的全部內容，希望文章能夠幫你解決所遇到的問題。

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