BZOJ1017 [JSOI2008]魔兽地图DotR

数据水。填坑。语文阅读题，看到都不想做。

就一树形dp。f[i][j][k]表示第i个物品，上供j个，花k块钱的代价。背包转移是O(m²)的，因为是一棵树所以转移次数是O(n)的，但是还要考虑j最大为100。一个技巧是合并完所有的东西之后再考虑把上供的烧掉。虽然这样的复杂度还是有点高。

毕竟我还是太弱啊，居然又花了一个上午。（虽然睡到十点）

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

struct edge {
	int t, v;
	edge *next;
};

const int maxm = 2009;
const int maxn = 53;
const int maxa = 103;

int n, m, f[maxn][maxa][maxm], ans[maxm], vl[maxn], vmax[maxn];
bool lf[maxn], ir[maxn];
edge elst[maxn], *ep(elst), *head[maxn];

inline void addEdge(int u, int v, int w) {
	ep-> t = v;
	ep-> v = w;
	ep-> next = head[u];
	head[u] = ep ++;
}

inline void upMax(int& a, int b) {
	if (a < b)
		a = b;
}

void mergeFunc(int* s, int* a, int* b) {
	static int r[maxm];
	memset(r, -1, sizeof(r));
	for (int i = 0; i <= m; ++ i)
		if (a[i] > -1)
			for (int j = 0; j + i <= m; ++ j)
				if (b[j] > -1)
					upMax(r[i + j], a[i] + b[j]);
	for (int i = 0; i <= m; ++ i)
		s[i] = r[i];
}

void dfsVMax(int p) {
	if (lf[p])
		return;
	vmax[p] = 100;
	for (edge* e = head[p]; e; e = e-> next) {
		dfsVMax(e-> t);
		vmax[p] = min(vmax[p], vmax[e-> t] / e-> v);
	}
}

void dfsDP(int p) {
	if (lf[p])
		return;
	for (int i = 0; i <= vmax[p]; ++ i)
		f[p][i][0] = 0;
	for (edge* e = head[p]; e; e = e-> next) {
		dfsDP(e-> t);
		for (int j = 0; j <= vmax[p]; ++ j)
			mergeFunc(f[p][j], f[p][j], f[e-> t][j * e-> v]);
	}
	for (int j = 1; j <= vmax[p]; ++ j)
		for (int k = 0; k < j; ++ k)
			for (int l = 0; l <= m; ++ l)
				if (f[p][j][l] > -1)
					upMax(f[p][k][l], f[p][j][l] + vl[p] * (j - k));
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif

	scanf("%d%d", &n, &m);
	memset(head, 0, sizeof(head));
	memset(f, -1, sizeof(f));
	memset(ir, 1, sizeof(ir));
	for (int i = 1; i <= n; ++ i) {
		char ty[3];
		scanf("%d%s", vl + i, ty);
		lf[i] = (ty[0] == 'B');
		if (lf[i]) {
			int b, c;
			scanf("%d%d", &c, &b);
			for (int j = 0; j <= b && c * j <= m; ++ j)
				for (int k = 0; k <= j; ++ k)
					upMax(f[i][k][j * c], (j - k) * vl[i]);
			vmax[i] = b;
		}
		else {
			int t, v, w;
			scanf("%d", &t);
			for (int j = 0; j < t; ++ j) {
				scanf("%d%d", &v, &w);
				addEdge(i, v, w);
				ir[v] = 0;
			}
		}
	}
	for (int i = 1; i <= n; ++ i)
		if (ir[i])
			dfsVMax(i);
	memset(ans, -1, sizeof(ans));
	ans[0] = 0;
	for (int i = 1; i <= n; ++ i)
		if (ir[i]) {
			dfsDP(i);
			mergeFunc(ans, ans, f[i][0]);
		}
	int s(0);
	for (int i = 0; i <= m; ++ i)
		upMax(s, ans[i]);
	printf("%d\n", s);
}