约翰开车回家，又准备顺路买点饲料了（咦？为啥要说“又”字？）回家的路程一共有 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、、、
代码如下：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
#define Maxn 510
#define Maxm 200010
#define LL long long struct node
{
LL d,sm,w;
}t[Maxn]; LL mymin(LL x,LL y) {return x<y?x:y;}
LL mymax(LL x,LL y) {return x>y?x:y;} bool cmp(node x,node y) {return x.d<y.d;} LL q[Maxm],st[Maxm],f[Maxm]; int main()
{
LL v,s,n;
scanf("%lld%lld%lld",&v,&s,&n);
for(LL i=;i<=n;i++) scanf("%lld%lld%lld",&t[i].d,&t[i].sm,&t[i].w);
sort(t+,t++n,cmp);
for(LL i=;i<=n;i++) t[i].d=s-t[i].d;
memset(f,,sizeof(f));
f[]=;
int ql,qr;
for(LL i=;i<=n;i++)
{
ql=qr=;q[qr]=;st[qr]=;
for(LL j=;j<=v;j++)
{
while(ql<qr&&(j-st[ql])>t[i].sm) ql++;
LL now=f[j];
f[j]=mymin(f[j],q[ql]+t[i].d*j*j+t[i].w*j);
while(now-j*j*t[i].d-t[i].w*j<=q[qr]&&qr>=ql) qr--;
q[++qr]=now-j*j*t[i].d-t[i].w*j;st[qr]=j;
}
}
printf("%lld\n",f[v]);
return ;
}
2016-10-20 09:14:21