题目链接
https://www.luogu.com.cn/problem/P1064
解题思路
如果我们直接用动态规划的模板去处理的话，我们很难去处理选择附件时的主件选择；
我的一开始的思路是在输入过程中把主件的值加到附件上，但由于每个主件的附件不唯一且主件可以单独选择，就很难处理；
后来换了一种思路，只对主件进行处理：
·因为附件是依赖于主件的，所以我们可以在遍历主件时，对每个主件的附件进行选择；
·在输入的时候把值分成两部分:main_w[]与attach_w[][]分别存储主件与附件；
·attach_w[i][j]表示主件i的第j个附件的费用；
·这样我们的状态转移方程就可以改为：
dp[j]=max(dp[j],dp[j-main_w[i]]+main_c[i]);
//选择主件
if(j>=main_w[i]+attach_w[i][1])
dp[j]=max(dp[j],dp[j-main_w[i]-attach_w[i][1]]+main_c[i]+attach_c[i][1]);
//选择主件+第一个附件
if(j>=main_w[i]+attach_w[i][2])
dp[j]=max(dp[j],dp[j-main_w[i]-attach_w[i][2]]+main_c[i]+attach_c[i][2]);
//选择主件+第二个附件
if(j>=main_w[i]+attach_w[i][2]+attach_w[i][1])
dp[j]=max(dp[j],dp[j-main_w[i]-attach_w[i][2]-attach_w[i][1]]+main_c[i]+attach_c[i][2]+attach_c[i][1]);
//选择主件+两个附件
代码展示
#include<bits/stdc++.h>
using namespace std;
const int maxn=32005;
/*
思路:
6200
1500 7
500 1 0
400 4 0
300 5 1
400 5 1
200 5 0
500 4 0
400 4 0
怎么能保证选择一个附件之后
*/
int main_w[70];
int main_c[70];
int attach_w[70][3];
int attach_c[70][3];
int dp[maxn];
int rely[70][70];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
if(c!=0){
attach_w[c][0]++;
attach_w[c][attach_w[c][0]]=a;
attach_c[c][attach_w[c][0]]=a*b;
}
else {
main_w[i]=a;
main_c[i]=a*b;
}
}
//初始化
for(int i=1;i<=m;i++){
for(int j=n;main_w[i]!=0&&j>=main_w[i];j--){
dp[j]=max(dp[j],dp[j-main_w[i]]+main_c[i]);
if(j>=main_w[i]+attach_w[i][1])
dp[j]=max(dp[j],dp[j-main_w[i]-attach_w[i][1]]+main_c[i]+attach_c[i][1]);
if(j>=main_w[i]+attach_w[i][2])
dp[j]=max(dp[j],dp[j-main_w[i]-attach_w[i][2]]+main_c[i]+attach_c[i][2]);
if(j>=main_w[i]+attach_w[i][2]+attach_w[i][1])
dp[j]=max(dp[j],dp[j-main_w[i]-attach_w[i][2]-attach_w[i][1]]+main_c[i]+attach_c[i][2]+attach_c[i][1]);
}
}
cout<<dp[n]<<endl;
return 0;
}