专栏文章

题解：P1064 [NOIP 2006 提高组] 金明的预算方案

DDeepSleep_Zzz
P1064题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miq5oi2v
此快照首次捕获于
2025/12/03 23:22
3 个月前
此快照最后确认于
2025/12/03 23:22
3 个月前
查看原文
begin
P1064 [NOIP 2006 提高组] 金明的预算方案

题目大意

给你一堆物品的价格和重要程度，这些物品分为主件和附件，其中每个主件最多有两个附件，求在给定价格内每件物品的价格与重要程度的乘积的总和最大是多少。

分析

这题看起来挺唬人的，其实扒了外皮就是个背包，只不过多了个主件附件的问题。

思路

既然买了附件就必须买主件，那我们不妨将它们绑定在一起，然后枚举每一个主件的购买方式。
对于每一次购买，只会出现以下 55 种购买方式：
  • 什么都不买。
  • 只买主件。
  • 买主件和第一个附件。
  • 买主件和第二个附件。
  • 买主件和全部两个附件。
我们只要把这五种情况的价值套一下背包板子算出来，取一下最大值即可。
至于如何绑定主件和附件，我们可以定义一个数组 soni,3son_{i,3}，其中 soni,0son_{i,0} 表示其附件的个数（其实也可以不要，但是我太懒），soni,1son_{i,1} 表示其第一个附件的编号，soni,2son_{i,2} 同理。

动态转移方程

我们设 dpjdp_j 为花费 jj 元所能得到的最大答案，那么有：
dpj=max⁡(dpj,dpj−vi+vi×wi)dp_j=\max(dp_j,dp_{j-v_i}+v_i\times w_i)
ii 表示物体编号，从 11 枚举到 mm。
jj 表示此时背包的容积（价格），从 nn 倒着枚举到 00。
不难发现，这玩意实际上就是一个 01 背包板子。

Code

CPP
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
ll n,m,v[70],w[70],c[70],dp[32010],son[70][3],q[70];
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for (ll i=1;i<=m;i++)
    {
        cin>>v[i]>>w[i]>>q[i];
        c[i]=v[i]*w[i]; // 只是因为我懒得写乘号
        if (q[i]) son[q[i]][++son[q[i]][0]]=i; // 绑定
    }
    for (ll i=1;i<=m;i++) // 背包板子
    {
        for (ll j=n;j>=0;j--)
        {
            if (q[i]) continue; // 我们只考虑主件
            if (j>=v[i]) // 够买主件
                dp[j]=max(dp[j],dp[j-v[i]]+c[i]);
            if (son[i][1] && j>=v[i]+v[son[i][1]]) // 够买主件和附件1
                dp[j]=max(dp[j],dp[j-v[i]-v[son[i][1]]]+c[i]+c[son[i][1]]);
            if (son[i][2] && j>=v[i]+v[son[i][2]]) // 够买主件和附件2
                dp[j]=max(dp[j],dp[j-v[i]-v[son[i][2]]]+c[i]+c[son[i][2]]);
            if (son[i][0]>=2 && j>=v[i]+v[son[i][1]]+v[son[i][2]]) // 够买主件和全部附件
                dp[j]=max(dp[j],dp[j-v[i]-v[son[i][1]]-v[son[i][2]]]+c[i]+c[son[i][1]]+c[son[i][2]]);
        }
    }
    cout<<dp[n];
    return 0;
}
end

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...