卖饲料——单调队列优化dp

题目描述

约翰开车来到镇上，他要带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元。 

思路

$dp[i][j]$表示到了$i$带有$j$吨饲料的最少花费。（注意此时i商店还没有买）

在每个商店我们可以选择买或者不买，枚举$i-1$之前带有的饲料$k$，那么$dp[i]][j]=min(dp[i-1][k]+j*j*(d[i]-d[i-1])+(j-k)*c[i])$

整理一下：$dp[i][j]=min(dp[i-1][k]-k*c[i]+j*j*(d[i]-d[i-1])+j*c[i])$

单调队列维护使dp[i-1][k]最小的 k转移即可。

code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int K=10010;
const int N=510;
LL f[N][K];
int k,hm,n;
struct FARM
{
    LL x,v,w;
}a[N];
LL d[N];

bool cmp(FARM a,FARM b)
{
    return a.x<b.x;
}

int main()
{
    scanf("%d%d%d",&k,&hm,&n);
    for(int i=1;i<=n;i++)scanf("%lld%lld%lld",&a[i].x,&a[i].v,&a[i].w);
    sort(a+1,a+1+n,cmp);
    n++;a[n]=(FARM){hm,0,0};
    for(int i=1;i<=n;i++)
    d[i]=a[i].x-a[i-1].x;
    memset(f,0x3f,sizeof(f));
    f[0][0]=0;
    for(int i=1;i<=n;i++)
    {
        deque<int>q;
        for(int j=0;j<=k;j++)
        {
            while(!q.empty()&&j-q.front()>a[i-1].v)q.pop_front();
            while(!q.empty()&&f[i-1][q.back()]-a[i-1].w*q.back()>=f[i-1][j]-a[i-1].w*j)
            q.pop_back();
            q.push_back(j);
            int p=q.front();
            if(!q.empty())f[i][j]=f[i-1][p]-a[i-1].w*p+a[i-1].w*j+j*j*d[i];

        }
    }
    cout<<f[n][k];
}