BZOJ1017 [JSOI2008]魔兽地图DotR

			    <div class="post_brief"><p>
数据水。填坑。语文阅读题，看到都不想做。</p>

就一树形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", &amp;n, &amp;m);
memset(head, 0, sizeof(head));
memset(f, -1, sizeof(f));
memset(ir, 1, sizeof(ir));
for (int i = 1; i &lt;= 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", &amp;c, &amp;b);
		for (int j = 0; j &lt;= b &amp;&amp; c * j &lt;= m; ++ j)
			for (int k = 0; k &lt;= j; ++ k)
				upMax(f[i][k][j * c], (j - k) * vl[i]);
		vmax[i] = b;
	}
	else {
		int t, v, w;
		scanf("%d", &amp;t);
		for (int j = 0; j &lt; t; ++ j) {
			scanf("%d%d", &amp;v, &amp;w);
			addEdge(i, v, w);
			ir[v] = 0;
		}
	}
}
for (int i = 1; i &lt;= n; ++ i)
	if (ir[i])
		dfsVMax(i);
memset(ans, -1, sizeof(ans));
ans[0] = 0;
for (int i = 1; i &lt;= n; ++ i)
	if (ir[i]) {
		dfsDP(i);
		mergeFunc(ans, ans, f[i][0]);
	}
int s(0);
for (int i = 0; i &lt;= m; ++ i)
	upMax(s, ans[i]);
printf("%d\n", s);

}

Comments