购买饲料Buying Feed

标签： 动态规划 背包DP

---

题目描述

约翰开车来到镇上，他要带KKK吨饲料回家。运送饲料是需要花钱的，如果他的车上有X吨饲料，每公里就要花费$X^2$元，开车D公里就需要$D×X^2$元。约翰可以从N家商店购买饲料，所有商店都在一个坐标轴上，第iii家店的位置是$Xi$​，饲料的售价为每吨$Ci$​元，库存为$Fi$​。

约翰从坐标$X=0$开始沿坐标轴正方向前进，他家在坐标$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$元。

输入输出格式

输入格式：

第1行:三个整数K,E,N 第2..N+1行:第i+1行的三个整数代表,Xi,Fi,Ci

输出格式：
一个整数,代表最小花费

输入输出样例

输入样例#1
2 5 3
3 1 2
4 1 2
1 1 1
输出样例#1
9

说明

$1≤K≤10000,1≤E≤500,1≤N≤500$
$0<Xi<E,1≤Fi≤10000,1≤Ci≤10^7$

题解

这道题用多重背包没什么说的，写在这里向强调的是在多重背包二进制优化的时候，我们必须转移以前的状态后才能转移当前二进制处理过的状态，比如这样

for(int k = V; k >= 1; k --) //不买
    f[i][k] = f[i - 1][k];   
for(int j = 1; j <= cnt[i]; j ++) //买
    for(int k = V; k >= p[i][j].s; k --)
        f[i][k] = min(f[i][k], f[i][k - p[i][j].s] + p[i][j].v);
        //多重背包要先转移前面的状态在二进制转换接下来的状态 
for(int k = V; k >= 1; k --) f[i][k] += k * k * (d[i + 1] - d[i]);

代码

#include<bits/stdc++.h>
#define N 510
#define ll long long
using namespace std;

ll V, e, n, x, y;
ll f[N][N * 20], d[N], cnt[N];
struct node{ll s, v;}p[N][20];
struct node2{ll d, x, y;}P[N];

bool cmp(node2 a, node2 b) {return a.d < b.d;}

int main()
{
    scanf("%lld%lld%lld", &V, &e, &n);
    for(int i = 0; i <= n; i ++)
        for(int j = 1; j <= V; j ++) f[i][j] = 1e18;
    for(int i = 1; i <= n; i ++) scanf("%lld%lld%lld", &P[i].d, &P[i].y, &P[i].x);
    sort(P + 1, P + n + 1, cmp);
    for(int i = 1; i <= n; i ++)
    {
        d[i] = P[i].d;
        ll x = P[i].x, y = P[i].y;
        int bin = 1;
        while(bin <= y) 
        p[i][++ cnt[i]].s = bin, p[i][cnt[i]].v = bin * x, y -= bin, bin <<= 1;
        if(y > 0) p[i][++ cnt[i]].s = y, p[i][cnt[i]].v = y * x;
    }
    d[0] = 0; d[n + 1] = e;
    for(int i = 1; i <= n; i ++)
    {
        for(int k = V; k >= 1; k --) //不买
            f[i][k] = f[i - 1][k];   
        for(int j = 1; j <= cnt[i]; j ++) //买
            for(int k = V; k >= p[i][j].s; k --)
                f[i][k] = min(f[i][k], f[i][k - p[i][j].s] + p[i][j].v);
        //多重背包要先转移前面的状态在二进制转换接下来的状态 
        for(int k = V; k >= 1; k --) f[i][k] += k * k * (d[i + 1] - d[i]);      
    } 
    printf("%lld", f[n][V]);            
    return 0;
}

心得

要注意转移的顺序和状态