banner

原题链接

https://www.luogu.com.cn/problem/P1064

解题思路

根据题意我们可以得知，只选主件、只选主件和第一个附件、只选主件和第二个附件、主件和两个附件都选这四种情况是互斥的，只能且必须任选其一，符合分组背包类似于“每组物品中只能选一个”的性质。由此可知，本题可以设法使用分组背包来做。我们根据题目特性，巧用预处理把问题转化为分组背包问题。

首先进行预处理，我们用一个结构体来存储物品的信息，把所有物品依照主附件关系分为若干组用vector容器v构建二维数组来存储。

在读入数据时，如果第i件物品是主件，那我们就把第i件物品的价格（DP时用到）和价格与重要度的乘积（更新答案时用到，以下都称“实际权重”）push_back到v[i]中；如果第i件物品是第j件物品的附件，那就把物品j按照如下规定的思路push_back到v[j]，v[i]留空即可。

根据四种互斥情况，我们规定每组物品：

  • 第一个物品的价格和实际权重等于主件；
  • 第二个物品的价格和实际权重等于主件+第一个附件；
  • 第三个物品的价格和实际权重等于主件+第二个附件；
  • 第四个物品的价格和实际权重等于主件+第一个附件+第二个附件；

又因为主件=第一个物品，主件+第一个附件=第二个物品，故上述规定可以表示为：

  • 第一个物品的价格和实际权重等于主件；
  • 第二个物品的价格和实际权重等于第一个物品+第一个附件；
  • 第三个物品的价格和实际权重等于第一个物品+第二个附件；
  • 第四个物品的价格和实际权重等于第二个物品+第二个附件；

上述规定可以用一个for循环进行递推计算，每次加入新附件时在遍历已有该附件对应主件和该主件其它附件的同时进行累加，将累加后的结果push_back到末端即可。（具体请参照代码）

至此，预处理结束，设m件物品中有a件主件和m-a件附件，则这些物品已经被分为a组，每组物品以主件开头，最多4件物品（根据题目数据，附件是一定出现在主件之后的）。

问题已经彻底转化成了一个分组背包问题，直接套用分组背包DP的模板求解即可。

参考代码

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
#include<cstdio>
#include<vector>
using namespace std;
struct good{int w,t;};
vector<good> v[61];
int n,m,a,b,c,f[32001];
int max(int x,int y){return x>y?x:y;}
int main()
{
  scanf("%d%d",&n,&m);
  for(int i=1;i<=m;i++)
    {
      scanf("%d%d%d",&a,&b,&c);
      int temp=v[c].size();//提前记录当前主件和该主件已出现的附件的总数，避免后面出现死循环
      if(!c)v[i].push_back({a,a*b});//处理主件
      else for(int k=0;k<temp;k++)
         v[c].push_back({a+v[c][k].w,a*b+v[c][k].t});//依据题解中规则处理附件
    }
  //一维分组背包模板
  for(int i=1;i<=m;i++)
    for(int j=n;j>=0;j--)
      for(int k=0;k<v[i].size();k++)
    {
      good now=v[i][k];
      if(j>=now.w)f[j]=max(f[j],f[j-now.w]+now.t);
    }
  printf("%d",f[n]);
  return 0;
}