A103.金明的预算方案

代码和思路和其他题解不太一样
感觉更好理解

没思路看

全篇中
$a_i=v_i*p_i$(即物品重要度）
$p$数组表示$q$数组

这题难度是不是评的有点高
因该是下位普及/提高+

题意

给定一些主件
再给定一些附件
买附件就必须买主件
求最多能获得多少重要度

分析

但是这个问题似乎有些复杂
我们可以分析一下

先不考虑选附件的情况
化为：
取一个主件或不取一个主件可以获得的最大重要度
方程为
$dp_i$表示有$i$元时可以取到的最大重要度

$v_j\le i\le n$

$dp_i=$ $\tt max$$(dp_i,选择第j个的最优解)$

难点

如果有附件，那么附件怎么选最优呢

其实根据以上分解
剩下的问题不就是

在背包容量为$i-v_j$的背包里
选择一些附件
价值: $v_k$
重要度: $a_k$

能让重要度最大

坑点

但有个问题
一个$dp_i$的值是取第$j$个主件的附件时
如果不选这个主件
这样不就是只选附件不选主件吗
不就错了吗

所以
应该用一个新的$f$来表示
选主件是的最值

则方程为
$v_k\le i\le i-v_j$

$f_i=$ $\tt max$$(f_i,$$\tt max$$(dp_{i-v_k},f_{i-v_k})+a_k)$
所以算完附件最值了
现在要算整体最值了
方程为
$v_j\le i\le n$
$dp_i=$ $\tt max$$(dp_i,$$\tt max$$(dp_{i-v_j},f_{i-v_j})+a_j)$

代码

#include<bits/stdc++.h>
#define int long long

using namespace std;
int n,m,dp[32010],f[32010];
int v[65],a[65],p[65];
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>v[i]>>a[i]>>p[i];
		a[i]*=v[i];
	}
	for(int i=1;i<=m;i++){
		if(p[i])continue;
		for(int k=1;k<=m;k++){//枚举附件
			if(p[k]!=i)continue;
			for(int j=n-v[i];j>=v[k];j--){
				f[j]=max(f[j],max(f[j-v[k]],dp[j-v[k]])+a[k]);
			}
			
		}
		for(int j=n;j>=v[i];j--)dp[j]=max(dp[j],max(f[j-v[i]],dp[j-v[i]])+a[i]);
	//	for(int j=n;j>=1;j--)cout<<dp[j]<<' ';
	//	cout<<endl;
		memset(f,0,sizeof f);
			
	}
	cout<<dp[n];
	return 0;
}