题意
有 $N$ 个商店，每个商店在 $X_i$，有 $F_i$ 个物品，价格为 $C_i$ 元。如果车上有 $P$ 个物品，每单位距离的运输费用为 $P^2$ 。从 $1\rightarrow E$，要求买 $M$ 个物品，求最小花费。
$N,E\le 500 \ , \ X_i\le E$ 。
题解
先把 $E$ 看成一个商店，各项属性为 $X_i=E \ , \ F_i=C_i=0$ 。然后把所有商店按 $X$ 排序。
用 $f[i][j]$ 表示到了第 $i$ 个商店，之前买了 $j$ 个物品的最小花费；枚举到 $i-1$ 个商店之前的物品个数 $k$ ，方程式为：
$$f[i][j]=\min_{p\le j} f[i-1][k]+(X_i-X_{i-1})\times j^2 + (j-k)\times C_{i-1}$$
把与 $P$ 有关的项放在一起：
$$f[i][j]=\min_{p\le j} (f[i-1][k]-k\times C_{i-1})+(X_i-X_{i-1})\times j^2 + j\times C_{i-1}$$
很显然是一个单调队列优化DP了。但有些细节需要注意：
- $f[i-1][j]=inf$ 无法转移
- 队列可能为空所以计算答案时需要判断
- $k$ 可以 $=j$，所以要把 $j$ 入队后再计算答案（
我纠结了很久）
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read()
{
char ch=getchar(); ll f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
struct node {
ll x,c,f;
} s[505];
const ll inf=0x3f3f3f3f;
ll n,m,e,f[505][10005],q[10005];
signed main()
{
m=read(); e=read(); n=read();
for (ll i=1;i<=n;i++) s[i].x=read(),s[i].f=read(),s[i].c=read();
s[++n]=(node){e,0,0};
sort(s+1,s+n+1,[](const node &x,const node &y){ return x.x<y.x; });
memset(f,0x3f,sizeof(f));
f[0][0]=0;
for (ll i=1;i<=n;i++)
{
ll l=1,r=1; q[1]=0; f[i][0]=0;
for (ll j=1;j<=m;j++)
{
while (l<=r && j-q[l]>s[i-1].f) l++; //库存不足
if (f[i-1][j]!=inf)
{
while (l<=r && f[i-1][q[r]]-s[i-1].c*q[r]>=f[i-1][j]-s[i-1].c*j) r--;
q[++r]=j;
}
ll k=q[l];
if (l<=r) f[i][j]=f[i-1][k]+(s[i].x-s[i-1].x)*j*j+s[i-1].c*(j-k); //先入队再更新答案
}
}
return !printf("%lld",f[n][m]);
}