网站首页制作的过程,美团企业邮箱提额3000,wordpress 插件 推荐,网站建设边框约翰开车回家#xff0c;又准备顺路买点饲料了#xff08;咦#xff1f;为啥要说“又”字#xff1f;#xff09;回家的路程一共有 E 公里#xff0c;这一路上会经过 K 家商店#xff0c;第 i 家店里有 Fi 吨饲料#xff0c;售价为每吨 Ci 元。约翰打算买 N 吨饲料又准备顺路买点饲料了咦为啥要说“又”字回家的路程一共有 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 33 1 24 1 21 1 1 样例输出9 解释在离家较近的两家商店里各购买一吨饲料则花在路上的钱是 1 4 5花在店里的钱是2 2 4 【分析】 嗯啊还是好笨想了挺久。 先列DPf[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-ksm[i] 即 kx-sm[i] x按顺序枚举的话就有单调性了。 啊又是一道限制为主的单调队列ORZ、、、 代码如下 1 #includecstdio2 #includecstdlib3 #includecstring4 #includeiostream5 #includealgorithm6 #includequeue7 #includecmath8 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 xy?x:y;}
19 LL mymax(LL x,LL y) {return xy?x:y;}
20
21 bool cmp(node x,node y) {return x.dy.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 i1;in;i) scanf(%lld%lld%lld,t[i].d,t[i].sm,t[i].w);
30 sort(t1,t1n,cmp);
31 for(LL i1;in;i) t[i].ds-t[i].d;
32 memset(f,127,sizeof(f));
33 f[0]0;
34 int ql,qr;
35 for(LL i1;in;i)
36 {
37 qlqr1;q[qr]0;st[qr]0;
38 for(LL j1;jv;j)
39 {
40 while(qlqr(j-st[ql])t[i].sm) ql;
41 LL nowf[j];
42 f[j]mymin(f[j],q[ql]t[i].d*j*jt[i].w*j);
43 while(now-j*j*t[i].d-t[i].w*jq[qr]qrql) 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
