题解 – P1064 [NOIP2006 提高组] 金明的预算方案

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

题目大意

有 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;
}