题解 P4544 【[USACO10NOV]购买饲料Buying Feed】

· · 题解

首先先考虑朴素dp，设f[i][j]为到了第i家店，1~i-1家店共买了j吨饲料

那么转移可以写成 ：

f[i][j]=min(f[i][j],f[i-1][k]+jjd[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]+jjd[i]+ja[i-1].w-ka[i-1].w)

提出来f[i-1][k]+jjd[i]+ja[i-1].w-ka[i-1].w

把属于k的提出来，变为f[i-1][k]-ka[i-1].w+jjd[i]+ja[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;
}