[文章目录]
Description
约翰开车来到镇上，他要带K吨饲料回家。运送饲料是需要花钱的，如果他的车上有X吨饲料，每公里就要花费X^2元，开车D公里就需要D* X^2元。约翰可以从N家商店购买饲料，所有商店都在一个坐标轴上，第i家店的位置是Xi，饲料的售价为每吨Ci元，库存为Fi。约翰从坐标X=O开始沿坐标轴正方向前进，他家在坐标X=E上。为了带K吨饲料回家，约翰最少的花费是多少呢？k<=10000 n<=500;
设dp[i][j] 表示第i个收费站已有j吨油的最小花费，然后在转移的时候计算运费，到下一个站点的时候，发现买油就是跑一个分组背包。又发现第一维可以省略，常数巨小。
好像ckh有O(nk)做法，好像是某单调队列优化神dp方程。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
ll w,e,n;
ll dp[11000];
struct node
{
int x,f,c;
}a[510];
bool cmp(node x,node y){return x.x<y.x;}
int main()
{
scanf("%lld%lld%lld",&w,&e,&n);
for(int i=1;i<=n;++i) scanf("%d%d%d",&a[i].x,&a[i].f,&a[i].c);
sort(a+1,a+n+1,cmp); memset(dp,0x3f,sizeof dp); dp[0]=0;
ll now=0,tmp,i,j,k,c,f;
for(i=1;i<=n;++i)
{
tmp=(a[i].x-now); now=a[i].x; c=a[i].c; f=a[i].f;
for(j=1;j<=w;++j) dp[j]+=tmp*j*j;
for(j=1;j<=f;f-=j,j<<=1)
for(k=w;k>=j;--k)
if(dp[k-j]+c*j<dp[k])
dp[k]=dp[k-j]+c*j;
if(f)
{
for(k=w;k>=f;--k)
if(dp[k-f]+c*f<dp[k])
dp[k]=dp[k-f]+c*f;
}
}
printf("%lld\n",dp[w]+(e-now)*w*w);
return 0;
}