洛谷 P2015 二叉苹果树 && caioj1107 树形动态规划（TreeDP）2：二叉苹果树

这道题一开始是按照caioj上面的方法写的

（1）存储二叉树用结构体，记录左儿子和右儿子

（2）把边上的权值转化到点上，离根远的点上

（3）用记忆化搜索，枚举左右节点分别有多少个点，去递归

这种写法有个好处，避免了总的树枝个数的枚举

#include<cstdio>

#include<algorithm>

#include<vector>

#include<cstring>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 112;

struct node

{

 	int v, w;

 	node(int v = 0, int w = 0) : v(v), w(w) {}

};

struct tree

{

	int l, r;

	tree() { l = r = 0; }

}a[MAXN];

vector<node> g[MAXN];

int f[MAXN][MAXN], n, q;

void dfs(int x, int fa)

{

	REP(i, 0, g[x].size())

	{

		int v = g[x][i].v, w = g[x][i].w;

		if(v == fa) continue;

		f[v][1] = w;

		if(!a[x].l) a[x].l = v;

		else a[x].r = v;

		dfs(v, x);

	}

}

int tree_dp(int x, int k)

{

	if(x == 0) return 0;

	if(f[x][k] != -1) return f[x][k];

	int maxt = 0;

	REP(i, 0, k)

	{

		int ls = i, rs = k - i - 1;

		maxt = max(maxt, f[x][1] + tree_dp(a[x].l, ls) + tree_dp(a[x].r, rs));

	}

	return f[x][k] = maxt;

}

int main()

{

	scanf("%d%d", &n, &q);

	REP(i, 0, n - 1)

	{

		int u, v, w;

		scanf("%d%d%d", &u, &v, &w);

		g[u].push_back(node(v,w));

		g[v].push_back(node(u,w));

	}

	memset(f, -1, sizeof(f));

	dfs(1, -1);

	REP(i, 1, n + 1) f[i][0] = 0;

	f[1][1] = 0;

	printf("%d\n", tree_dp(1, q + 1));

	return 0;

}

然后看到洛谷上还有更加简洁的写法

先往下搜索，然后回溯的时候记录边的数量，然后枚举左右节点

取多少树枝，取max。

f[u][j] = max(f[u][j-k-1] + f[v][k] + w);

然后这里用到了01背包的思想

树枝可以看成从的总的重量，所以要逆序

#include<cstdio>

#include<algorithm>

#include<vector>

#include<cstring>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 112;

struct node

{

 	int v, w;

 	node(int v = 0, int w = 0) : v(v), w(w) {}

};

vector<node> g[MAXN];

int f[MAXN][MAXN], b[MAXN], n, q;

void dfs(int u, int fa)

{

    REP(i, 0, g[u].size())

    {

        int v = g[u][i].v, w =  g[u][i].w;

        if(v == fa) continue;

        dfs(v, u);

        b[u] += b[v] + 1;

        for(int j = min(q, b[u]); j >= 0; j--)

        	for(int k = 0; k <= min(b[v], j - 1); k++)

                f[u][j] = max(f[u][j], f[u][j-k-1] + f[v][k] + w);

    }

}

int main()

{

    scanf("%d%d", &n, &q);

    REP(i, 1, n)

    {

        int u, v, w;

        scanf("%d%d%d", &u, &v, &w);

        g[u].push_back(node(v,w));

        g[v].push_back(node(u,w));

    }

    dfs(1, 0);

    printf("%d\n", f[1][q]);

    return 0;

}

做完了选课在来看这一题，又有新的感悟。

树上背包的做法适用于多叉树和二叉树，二叉树是两个物品，多叉树是多个物品。

而这道题有一点不同是权值是边。那么吸取上面写的经验。

我们可以把边的权值转移到离根远的点上，同时可以取的点数为边数+1

然后就一样啦！！

#include<cstdio>

#include<vector>

#include<algorithm>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 112;

int f[MAXN][MAXN], n, q;

struct node

{

	int v, w;

	node(int v = 0, int w = 0) : v(v), w(w) {}

};

vector<node> g[MAXN];

int dfs(int u, int fa)

{

	int sum = 1;

	REP(i, 0, g[u].size())

	{

		int v = g[u][i].v, w = g[u][i].w;

		if(v == fa) continue;

		f[v][1] = w;

		int t = dfs(v, u);

		sum += t;

		for(int j = sum; j >= 1; j--)

			for(int k = 0; k <= min(t, j - 1); k++)

				f[u][j] = max(f[u][j], f[u][j-k] + f[v][k]);

	}

	return sum;

}

int main()

{

	scanf("%d%d", &n, &q);

	REP(i, 0, n - 1)

	{

		int u, v, w;

		scanf("%d%d%d", &u, &v, &w);

		g[u].push_back(node(v, w));

		g[v].push_back(node(u, w));

	}

	dfs(1, -1);

	printf("%d\n", f[1][q+1]);

	return 0;

}

巴特西

洛谷 P2015 二叉苹果树 && caioj1107 树形动态规划（TreeDP）2：二叉苹果树

最新文章

热门文章