Description
约翰开车来到镇上，他要带K吨饲料回家。运送饲料是需要花钱的，如果他的车上有X吨饲料，每公里就要花费X^2元，开车D公里就需要D*
X^2元。约翰可以从N家商店购买饲料，所有商店都在一个坐标轴上，第i家店的位置是Xi，饲料的售价为每吨Ci元，库存为Fi。
约翰从坐标X=O开始沿坐标轴正方向前进，他家在坐标X=E上。为了带K吨饲料回家， 约翰最少的花费是多少呢？假设所有商店的库存之和不会少于K。
举个例子，假设有三家商店，情况如下所示：
坐标 X=1 X=3 X=4 E=5
库存 1 1 1
售价 1 2 2
如果K=2，约翰的最优选择是在离家较近的两家商店购买饲料，则花在路上的钱是1+4=5，花在商店的钱是2+2=4，共需要9元。
Input
第1行:三个整数K,E,N 第2..N+1行:第i+1行的三个整数代表,X_i,F_i,C_i.
Output
一个整数,代表最小花费
Sample Input
2 5 3
3 1 2
4 1 2
1 1 1
Sample Output
9
题解
我的基础真的是辣鸡。一个dp都
写不好
首先先考虑朴素dp，设f[i][j]为到了第i家店，1~i-1家店共买了j吨饲料
那么转移可以写成
f[i][j]=min(f[i][j],f[i-1][k]+j*j*d[i]+(j-k)*a[i-1].w);
其中a[i-1].w为第i-1家店饲料的价格，d[i]为第i与i-1家店的距离
复杂度为O(nk^2)，很明显炸了
怎么办？？先把式子拆了吧
f[i][j]=min(f[i][j],f[i-1][k]+j*j*d[i]+j*a[i-1].w-k*a[i-1].w)
提出来f[i-1][k]+j*j*d[i]+j*a[i-1].w-k*a[i-1].w
把属于k的提出来，变为f[i-1][k]-k*a[i-1].w+j*j*d[i]+j*a[i-1].w
可以发现，后半部分是定值，我们用单调队列维护前半部分就好了
但是如果单纯的单调队列会错，为啥？如果我这家店所能提供的饲料不够我需要的呢？
所以，还要加上几个特判啦
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
const LL inf=1e15;
struct node
{LL x,c,w;//距离 数量 价格
}a[11000];
bool cmp(node n1,node n2){
return n1.x<n2.x;}
LL f[510][11100];//第i家店 1~i-1家店装了j吨饲料
int n,m,kk;//n家店 距离m 希望买kk
LL d[11000];
LL list[11000],head,tail;
int main()
{freopen("feed.in","r",stdin);freopen("feed.out","w",stdout);scanf("%d%d%d",&kk,&m,&n);for(int i=1;i<=n;i++)scanf("%lld%lld%lld",&a[i].x,&a[i].c,&a[i].w);n++;a[n].x=m;sort(a+1,a+1+n,cmp);for(int i=2;i<=n;i++)d[i]=a[i].x-a[i-1].x;for(int i=0;i<=n;i++)for(int j=0;j<=kk;j++)f[i][j]=inf;f[0][0]=0;for(LL i=1;i<=n;i++){head=tail=0;for(LL j=0;j<=kk;j++){while(head<tail && j-list[head]>a[i-1].c)head++;//需要买的 本商店不能满足 if(f[i-1][j]!=inf){while(head<tail){LL k=list[tail-1];if(f[i-1][k]-k*a[i-1].w<f[i-1][j]-j*a[i-1].w)break;tail--;}list[tail++]=j;}if(head<tail){LL k=list[head];f[i][j]=f[i-1][k]+(j-k)*a[i-1].w+j*j*d[i];}}}printf("%lld\n",f[n][kk]);return 0;
}