BZOJ 1812 Riv

发表于 | 更新于

Link

轻车熟路，独立A掉，Cool！

Solution

可以注意到，每个点对答案的贡献取决于它到它的祖先中离它最近的伐木场的距离。按照套路，设计状态f[i][j][d]f[i][j][d]表示在以ii为根的子树内，建了jj个伐木场，ii点到最近的伐木场距离为dd，这棵子树对答案的最小贡献。 笼统地说dd是距离，但是直接表示是不好表示的。所以就做个转化，相当于离散化，用dd表示最近的伐木场的深度，这样也可以很方便地转移。 于是考虑f[i][j][d]f[i][j][d]的转移。 通过观察，可以得到一个性质：一个点pp，与它的任意子节点uu，要么dd相同，要么d[u]==depth[u]d[u]==depth[u]，即uu上建了伐木场。你说这个还叫性质？不是一眼秒的东西嘛。好吧当我没说 然后就可以分情况讨论转移了。 然后这里又涉及背包的合并，我想当然地写完，发现输出00。 最后发现，一开始设置的合法状态的00和任何的值取min都是它本身。苦思冥想得不到结果，最后得出的结论是要求用最小代价把背包填满的多重背包不能用滚动数组。。（如果可以的话还请指教）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=111,INF=0x7f7f7f7f;
using std::vector;
using std::min;
int sum(int x,int y){return x==INF||y==INF?INF:x+y;}
int dis[MAXN],fs[MAXN][MAXN],w[MAXN],fa[MAXN],n,m,f[MAXN][MAXN][MAXN],g[MAXN][MAXN][MAXN],dep[MAXN];
int son[MAXN][MAXN];
int cost(int id,int d){return (dis[id]-dis[fs[id][d]])*w[id];}
void DP(int pos)
{
	static int Pack[MAXN][MAXN];
	#define Reset(x) (memset(x,127,sizeof(x)),x[0][0]=0)
	int *sons=son[pos],sonc=sons[0];
	for(int i=1;i<=sonc;i++) DP(sons[i]);
	if(pos)
	{
		Reset(Pack);
		for(int i=1;i<=sonc;i++)
		{
			int u=sons[i];
			for(int j=m-1;~j;j--)
				for(int k=0;k<=j;k++)
					chkmn(Pack[i][j],sum(Pack[i-1][j-k],min(f[u][k][dep[pos]],f[u][k][dep[u]])));
		}
		for(int j=m-1;~j;j--)
			f[pos][j+1][dep[pos]]=sum(Pack[sonc][j],cost(pos,dep[pos]));
		for(int d=0;d<dep[pos];++d)
		{
			Reset(Pack);
			for(int i=1;i<=sonc;i++)
			{
				int u=sons[i];
				for(int j=m;~j;j--)
					for(int k=0;k<=j;k++)
						chkmn(Pack[i][j],sum(Pack[i-1][j-k],min(f[u][k][d],f[u][k][dep[u]])));
			}
			for(int j=m;~j;j--)
				f[pos][j][d]=sum(Pack[sonc][j],cost(pos,d));
		}
	}
	else
	{
		f[pos][0][0]=0;
		Reset(Pack);
		for(int i=1;i<=sonc;i++)
		{
			int u=sons[i];
			for(int j=m;~j;j--)
				for(int k=0;k<=j;k++)
					chkmn(Pack[i][j],sum(Pack[i-1][j-k],min(f[u][k][0],f[u][k][1])));
		}
		for(int j=m;~j;j--) f[pos][j][0]=Pack[sonc][j];
	}
}
void DFS(int pos)
{
	for(int i=1;i<=son[pos][0];i++)
	{
		dep[son[pos][i]]=dep[pos]+1;
		dis[son[pos][i]]+=dis[pos];
		DFS(son[pos][i]);
	}
}
int main()
{
	get(n),get(m);
	for(int i=1;i<=n;i++)
	{
		get(w[i]),get(fa[i]),get(dis[i]);
		son[fa[i]][++son[fa[i]][0]]=i;
	}

	DFS(0);
	for(int i=0;i<=n;i++)
	{
		int p=i;
		while(p) 
			fs[i][dep[p]]=p,p=fa[p];
	}
	memset(f,127,sizeof(f));
	DP(0);
	printf("%d\n",f[0][m][0]);
	return 0;
}
/* AC Record(Bugs) *
 * 
 * * * * * * * * * */