【题解】洛谷 P4037 [JSOI2008] 魔兽地图 [树上背包]-CSDN博客

#include<bits/stdc++.h>
using namespace std;
 
const int N = 55, M = 2010;
//2 * N 多开点，之后会有莫名其妙的东西炸掉 
int f[N][2 * N][M];     //f[x][i][j]表示处理武器 x 时，预留 i 个 x 用于合成更高级装备，
                    //最后花费 j 金币能获得的最大力量值
int p[N], a[N];      //p[N]: 装备提供的力量
				     //a[N]: 基本装备的单价，高级装备是合成所需的总金币
int sum[N];          //sum[x]：武器 x最多能购买的数量 
int ans[M];          //最后答案存储 
int n, m;
 
struct node {
	int y, num;
} ;
vector<node> G[N];   //我用 vector 存武器之间的依赖关系
bool v[N];   // v[x]：1 代表 x 不是最高端的武器，反之 0 代表是 
bool b[N];   // b[x]：1 代表 x 已经 dfs 过，反之 0 代表还没有
int g[M];    //临时最大值存储 
 
void dfs(int x) {
	if (b[x]) {   //节省时间 
		return ;
	}
	b[x] = 1;
	
	if (G[x].size() == 0) {   //如果是最低端的武器 
		sum[x] = min(sum[x], m / a[x]);
		for (int i = 0; i <= sum[x]; i++) {   //合成武器 x 的数量
			for (int j = 0; j <= i; j++) {    //转化为力量值的数量
				f[x][i - j][i * a[x]] = p[x] * j;
			}
		}
		return ;    //处理完了就退出 
	}
	
	sum[x] = 1e9;    //初始化最大值 
	for (auto i: G[x]) {
		dfs(i.y);        //递归 y 
		sum[x] = min(sum[x], sum[i.y] / i.num);
		a[x] += i.num * a[i.y];    //累计花费值 
	}
	sum[x] = min(sum[x], m / a[x]);
	
	for (int i = 0; i <= sum[x]; i++) {  // i: 总合成 x 数量
		int g[M];
		memset(g, -0x3f, sizeof(g)); g[0] = 0;
		//为什么负无穷？见主函数 f 初始化 
		
		for (auto j: G[x]) {
			for (int ga = m; ga >= 0; ga--) {   //当前 x 武器总使用金币数  
				int t = -1e9;   //最大值初始化
				//为什么负无穷？见主函数 f 初始化 
				 
				for (int gb = 0; gb <= ga; gb ++) {   //分配给当前 y 的金币数 
					t = max(t, g[ga - gb] + f[j.y][i * j.num][gb]);
			//g[ga  -gb]: 花费 ga - gb 金币在之前的 y 上能获得的最大力量值
			//f[j.y][i * j.num][gb]：预留 i * j.num个 y，因为你要 i 个 x，花费 gb 个金币 
					
			//关于 ga 为什么要倒着遍历，因为我们不能取当前 y 武器更新过的 g[ga - gb]
			//只能使用上一个合成 x 需要的低端武器的 g
					g[ga] = t;    //更新当前 g 
				}
			}
		}
		
		//全部 y 都递归完了，合并 
		for (int j = 0; j <= i; j++) {   //预留的 x 的数量
			for (int k = 0; k <= m; k++) {   //总共花的金币
				f[x][j][k] = max(f[x][j][k], g[k] + p[x] * (i - j));
			}
		} 
	}
	//自己想想为什么按照这个顺序枚举更新，
	//for (int i = 0; i <= sum[x]; i++) 和 for (auto j: G[x])可以调换位置吗？ 
} 
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> m;
	memset(v, 0, sizeof(v));
	
	for (int i = 1; i <= n; i++) {
		cin >> p[i];
		
		char s[5];  //得开多点，防止奇怪的空格 
		cin >> s;
		if (s[0] == 'A') {
			int C;
			cin >> C;
			for (int j = 1; j <= C; j++) {
				node mt;
				cin >> mt.y >> mt.num;
				v[mt.y] = 1;
				G[i].push_back(mt);
			} 
		}
		else {
			cin >> a[i] >> sum[i];
		}
	}
	
	memset(f, -0x3f, sizeof(f));
	//为什么要负无穷？因为如果 f[i][j][k] 中间的 j 是你真的要预留 k 个才可以合法的
	//毕竟之后递归的时候要用到。 
	memset(ans, 0, sizeof(ans)); 
	//为什么都是 0？你最少也就只能拥有 0 个力量
	 
	for (int i = 1; i <= n; i++) if(!v[i]) {   //如果是最高端的武器 
		dfs(i);              //先递归处理 
		for (int j = m; j >= 0; j--) {   //总花费金币数量 
			for (int k = 0; k <= j; k++) {    //真正给 i 使用的金币数量 
				ans[j] = max(ans[j], ans[j - k] + f[i][0][k]);
				// f[i][0][k]表示不预留 i，花费 k 金币能获得的最大力量值
				//关于这里为什么 j 是倒着枚举的，因为我们不能取当前 i 武器更新过的 ans[j - k]
				//只能使用上一个最高端武器的 ans 
			}
		}
	}
	cout << ans[m] << "\n";
	
	return 0;
}