题解 - P1064 金明的预算方案

[题目链接] 金明的预算方案

题目大意

有 $n$ 块钱，$m$ 个物品，有些物品是主件，有些物品是附件，主件和附件的关系是：一个主件最多两个附件，选附件必须选主件。每个物品有一个权值 $w$ ，有一个花费 $v$ 物品的贡献为 $w * v$，求最大贡献。

输入格式

第一行有两个整数，分别表示总钱数 $n$ 和希望购买的物品个数 $m$。

第 $2$ 到第 $(m + 1)$ 行，每行三个整数，第 $(i + 1)$ 行的整数 $v_i$，$p_i$，$q_i$ 分别表示第 $i$ 件物品的价格、重要度以及它对应的的主件。如果 $q_i=0$，表示该物品本身是主件。

---

做法

直接说做法：01背包，每次取的时候只取主件，这个主件可以带着附件一起取。这样有4种方案：

• 只取自己
• 取自己和第一个附件
• 取自己和第二个附件
• 取自己和两个附件 最后注意一下条件判断，当前枚举到的花费要大于其加上孩子的花费。 很容易证明，这样取是跟普通背包没有区别的。

AC Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxd(x, y) ((x) > (y) ? (x) : (y))
#define mind(x, y) ((x) < (y) ? (x) : (y))
#define abs_sub(x, y) ((x) > (y) ? (x) - (y) : (y) - (x))
const double eps = 1e-8;
const double pi = acos(-1.0);
const int N = 3210, M = 100;
int dp[N];
int n, m;
int cost[M], w[M], cls[M], lock[M], W[M];
vector<int> T[M];
int main()
{
  scanf("%d%d", &n, &m);
  n /= 10;
  int a, b, c;
  for(int i = 1; i <= m; i++) {
    scanf("%d%d%d", &a, &b, &c);
    cost[i] = a / 10, w[i] = b, W[i] = cost[i] * w[i], cls[i] = c;
    T[c].emplace_back(i);
  }
  for(int i = 1; i <= m; i++) {
    for(int j = n; j >= cost[i]; j--) {
      if(cls[i] == 0) dp[j] = maxd(dp[j], dp[j - cost[i]] + W[i]);
      if(T[i].size() >= 1) {
        if(j >= cost[i] + cost[T[i][0]]) dp[j] = maxd(dp[j], dp[j - cost[i] - cost[T[i][0]]] + W[i] + W[T[i][0]]);
      }
      if(T[i].size() == 2) {
        if(j >= cost[i] + cost[T[i][1]]) dp[j] = maxd(dp[j], dp[j - cost[i] - cost[T[i][1]]] + W[i] + W[T[i][1]]);
        if(j >= cost[i] + cost[T[i][1]] + cost[T[i][0]]) dp[j] = maxd(dp[j], dp[j - cost[i] - cost[T[i][0]] - cost[T[i][1]]] + W[i] + W[T[i][0]] + W[T[i][1]]);
      }
    }
  }
  printf("%d\n", dp[n] * 10);
  return 0;
}