5.1 考试下饭合集

补充题 可怜与超市

啊啊啊啊终于有一道我能想出来的题了好鸡冻好鸡冻啊啊啊啊啊
终于不是熟练剖分那种阴间题了啊啊啊啊啊
（要不是因为菜的不行考试啥也不会也不至于这么疯狂）
嗯哼看题......

遇到这种题目哈，啥也不说先打一遍树形背包的板子爽一下（f[i][j]）
爽完就发现不对劲了......
首先就是这个蜜汁数据范围，价格能到了1e9
这种数据范围，或许就只有wcr巨佬开十万乘十万的bool数组的操作才能与之比肩吧......
所以转变思路，f[i][j]代表在i节点，买j个物品所用的价格
最后再遍历一遍f[1][i]，如果f[1][i] <= b的话ans = max（ans, i）
老套路了~
再而就是注意到物品可以用优惠券也可以不用优惠券，但儿子要用他亲爱的父亲也就必须用，所以f再多开一维代表当前节点优惠券用还是不用，方便转移(0为不用，1为用)

好了开始转移：(当前节点为u， 儿子为v)
基本就是套路模式，两层循环j和k,j 代表当前节点总共买的物品数，k代表给儿子分配的物品数。其中，j 的范围是size[u] 到 0，k 的范围是min（j, size[v]） 到 0 。那么转移方程就是:
f[u][j][0] = min(f[u][j][0], f[u][j-k][0] + f[v][k][0]);
f[u][j][1] = min(f[u][j][1], f[u][j-k][1] + min(f[v][k][1], f[v][k][1]));
注意一点，那就是本题只有“是否使用优惠券”成树形结构，然而所有物品都可以买或者不买，所以j == k的情况存在，即直接不买当前节点。但连这个节点都不买，还怎么用优惠券？所以第二个方程必须满足条件j > k
然后，你就愉快地T掉了
注意，这种状态转移的写法，因为j要从size[u]循环到0,k最少也要从j到0,那么复杂度就接近\n^3,不T才怪。。。所以我们换一种写法：
j代表此前儿子买下的物品总数，k代表当前儿子的物品数，
f[u][j+k][0] = min(f[u][j+k][0], f[u][j][0] + f[v][k][0]);
f[u][j+k][1] = min(f[u][j+k][1], f[u][j][1] + min(f[v][k][0], f[v][k][1]);
（复杂度暂时还没完全搞懂（捂脸哭），但反正它是能过掉的orz）

边界：(w代表价格，d代表优惠券降价)
f[u][1][1] = w[u] - d[u];
f[u][1][0] = w[u];
f[u][0][0] = 0;
因为总价格我们要算最小值，所以其他的f值初始化成inf就可以了

上代码：

#define inf 0x3f3f3f3f3f3f3f3f
#define ll long long
#define rl register int
using namespace std;

const int Maxn = 5e3 + 5;

struct Edge{
	int nxt, to;
}ed[Maxn * 2];

int n, b;
int d[Maxn], w[Maxn];
int head[Maxn], tot;

void add_edge(int u, int v){
	ed[++tot].nxt = head[u];
	ed[tot].to = v;
	head[u] = tot;
}

int size[Maxn];
ll f[Maxn][Maxn][2];
ll g[Maxn];

void dfs(int u){
	size[u] = 1;
	f[u][1][1] = w[u] - d[u], f[u][1][0] = w[u], f[u][0][0] = 0; 
	for(int i = head[u]; i; i = ed[i].nxt){
		int v = ed[i].to;
		dfs(v);			
		for(rl j = size[u]; j >= 0 ; --j){
			for(rl k = size[v]; k >= 0; --k){
				f[u][j+k][0] = min(f[u][j+k][0], f[v][k][0] + f[u][j][0]);
				f[u][j+k][1] = min(f[u][j+k][1], min(f[v][k][1], f[v][k][0]) + f[u][j][1]);
			}
		}
		size[u] += size[v];
	}		
}


int main(){
	scanf("%d %d", &n, &b);
	for(int i = 1; i <= n; i++){
		scanf("%d %d", &w[i], &d[i]);
		if(i > 1){
			int fa;
			scanf("%d", &fa);
			add_edge(fa, i);
		}
	}
	memset(f, inf, sizeof(f));
	dfs(1);
	int ans = 0;
	for(int i = 1; i <= n; i++){
		if(f[1][i][0] <= b || f[1][i][1] <= b){
			ans = i;
		}
	}
	printf("%d", ans);
	return 0;
}`