[bzoj1812][IOI2006]riv_多叉树转二叉树_树形dp

riv bzoj-1812 IOI-2006

题目大意：给定一棵n个点树，要求在上面建立k个收集站。点有点权，边有边权，整棵树的代价是每个点的点权乘以它和它的最近的祖先收集站的距离积的和。

注释：$1\le n \le 100$，$1\le k \le 50$。

---

想法：显然，这是一道树形dp题。状态也非常容易... ...只不过，我们好像要枚举子集...

所以，我们这里有一个黑科技：多叉树转二叉树。

我们先把它转成二叉树，然后再进行转移即可。

状态：dp[i][j][k]表示以i为根的子树中选出j个为伐木场且在i的祖先中距离i最近的伐木场为k时，将以i为子树的所有木头都运到k的最小花费。

转移略，傻逼转移。

最后，附上丑陋的代码... ...

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 110

#define K 60

using namespace std;

int rs[N],ls[N],dp[N][N][K],cost[N],fa[N],dist[N];

int flag,n,k;

void dfs(int pos)

{

	if(!pos&&flag) return; flag=1;

	dfs(ls[pos]); dfs(rs[pos]);

	int len=dist[pos];

	for(int i=fa[pos];i+1;i=fa[i])

	{

		for(int j=0;j<=k;j++)

		{

			for(int l=0;l<=j;l++)

			{

				if(j-l-1>=0)

					dp[pos][i][j]=min(dp[pos][i][j],dp[ls[pos]][pos][l]+dp[rs[pos]][i][j-l-1]);

				if(j-l>=0)

					dp[pos][i][j]=min(dp[pos][i][j],dp[ls[pos]][i][l]+dp[rs[pos]][i][j-l]+len*cost[pos]);

			}

		}

		len+=dist[i];

	}

}

int main()

{

	cin >> n >> k ;

	for(int i=1;i<=n;i++)

	{

		scanf("%d%d%d",&cost[i],&fa[i],&dist[i]);

		rs[i]=ls[fa[i]];

		ls[fa[i]]=i;

	}

	memset(dp,0x3f,sizeof dp);

	memset(dp[0],0,sizeof dp[0]);

	fa[0]=-1;

	dfs(0);

	printf("%d\n",dp[ls[0]][0][k]);

	return 0;

}

小结：好题，我们发现状态简单，转移需要让自己分担和的话，可以想想多叉树转二叉树。