(luogu1417) 烹调方案

发表于 分类于 ，

原题链接

思路:

乍一看像一个普通的 01 背包，但是每个物品的” 价值” 是与时间有关的， 所以不是个单纯的 01 背包.

同时考虑物品的顺序对结果有影响 , 所以不能只用 dp 解决.

考虑物品 \(i\) 与物品 \(j\), 假设已经花费时间 \(t\), 则先取 \(i\) 后取 \(j\) 增加的价值为:

\[ v_1 = a_i - (t+c_i)b_i + a_j - (t+c_i+c_j)b_j \]

先取 \(j\) 后取 \(i\) 为:

\[ v_2 = a_j - (t+c_j)b_j + a_i - (t+c_i+c_j)b_i \]

若 \(v_1 > v_2\), 则有:

也即，对于两个物品的序偶 \(< i, j >\), 如果满足上述不等式，则优先考虑 \(i\) 更优.

所以对物品按上述方式排序后， 按此排序进行 dp 就解决了物品考虑顺序的问题 (按此顺序比其他顺序一定更优), 剩下的就是 01 背包了.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <cstdio>
#include <algorithm>
using std::sort;
using std::max;
typedef long long LL;
const int Mn(55),Mt(100500);

struct Food {
    LL a,b,c;
    bool operator < (const Food& rhs) const {
        return rhs.c*b>rhs.b*c; //排序方式
    }
}arr[Mn];

LL dp[Mt];

int main() {
    int t,n;
    scanf("%d %d",&t,&n);
    for(int i(1);i<=n;++i) {
        scanf("%lld",&arr[i].a);
    }
    for(int i(1);i<=n;++i) {
        scanf("%lld",&arr[i].b);
    }
    for(int i(1);i<=n;++i) {
        scanf("%lld",&arr[i].c);
    }
    sort(arr+1,arr+n+1);    //排序
    //01背包
    for(int i(1);i<=n;++i) {
        Food& x(arr[i]);
        for(int j(t);j>=x.c;--j) {
            dp[j] = max(dp[j],dp[j-x.c]+x.a-1ll*j*x.b);
        }
    }
    //寻找答案
    LL ans(0);
    for(int i(0);i<=t;++i) {
        ans = max(ans,dp[i]);
    }
    printf("%lld",ans);
    return 0;
}