洛谷4544 [USACO10NOV]Buying Feed

题解 动态规划 动态规划-单调队列优化DP 提高+/省选-
题目链接 编辑文章

题意

有 $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了。但有些细节需要注意:

  1. $f[i-1][j]=inf$ 无法转移
  2. 队列可能为空所以计算答案时需要判断
  3. $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]);
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空