[JSOI2008]魔兽地图DotR tree_dp
#include <cstdio>#include <cstdlib>#include <cstring>#include <set>#include <map>#include <queue>#include <algorithm>using namespace std;#define maxn 52#define maxm 2001struct ed {int t; ed * n;};ed eds[maxn], * adj = eds, * edge[maxn];int n, m, ans;int w[maxn], gold[maxn], lim[maxn], num[maxn];int max1[maxn], fa[maxn], temp[maxm];int f[maxn][101][maxm];void link(int i, int j){* (++ adj) = (ed) {j, edge[i]}, edge[i] = adj, fa[j] = i;}bool up(int & i, int j) {return j > i ? i = j, 1 : 0;}bool pu(int & i, int j) {return j < i ? i = j, 1 : 0;}void dfs(int u){int i, j, k, v; ed * e;int (* ff)[maxm] = f[u];if (! edge[u]){max1[u] = min(lim[u], m / gold[u]);for (i = 0; i <= max1[u]; ++ i)for (j = i; j <= max1[u]; ++ j)up(ff[i][j * gold[u]], (j - i) * w[u]);return;}max1[u] = maxm;for (e = edge[u]; e; e = e->n)dfs(e->t), pu(max1[u], max1[e->t] / num[e->t]);for (i = 0; i <= max1[u]; ++ i) ff[i][0] = 0;for (e = edge[u]; e; e = e->n)for (i = 0; i <= max1[u]; ++ i){int (* gg)[maxm] = f[e->t];v = i * num[e->t];memcpy(temp, ff[i], sizeof ff[i]);memset(ff[i], 0xFF, sizeof ff[i]);for (j = m; j >= 0; -- j)for (k = j; k >= 0; -- k)if (~ temp[j - k] && ~ gg[v][k])if (up(ff[i][j], temp[j - k] + gg[v][k]))up(ans, ff[i][j]);}for (i = 0; i < max1[u]; ++ i)for (j = max1[u]; j > i; -- j)for (k = m; k >= 0; -- k)if (~ ff[j][k])if (up(ff[i][k], ff[j][k] + (j - i) * w[u]))up(ans, ff[i][k]);}int main(){freopen("1017.in", "r", stdin);freopen("1017.out", "w", stdout);int i, j, k;scanf("%d%d", & n, & m);memset(f, 0xFF, sizeof f);for (i = 1; i <= n; ++ i){scanf("%d ", w + i);if (getchar() == 'B')scanf("%d%d", gold + i, lim + i);elsefor (scanf("%d", & j); j --; ){scanf("%d", & k), link(i, k);scanf("%d", num + k);}}for (i = 1; i <= n; ++ i)if (! fa[i]) dfs(i);printf("%d\n", ans);return 0;}