洛谷p2015二叉苹果树&yzoj1856多叉苹果树题解

二叉

多叉

有一棵苹果树，如果树枝有分叉，可以是分多叉，分叉数k>=0（就是说儿子的结点数大于等于0）这棵树共有N个结点（叶子点或者树枝分叉点），编号为1~N，树根编号一定是1。我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。

数据规模：

对于20%的数据，满足1 <= n <=15。

对于40%的数据，满足1 <= n <=100。

对于100%的数据，满足1 <= n <=310，c<=2^31-1。

两道树形DP题，一样的代码改下细节就能过，令f[x][y]表示以x为根的子树保留y条边最多苹果数，易得出状态转移方程

f[x][[t]=max(f[x][t] , f[x][t-j-1] + f[y][j]+edge[i])

其中y是x的子节点，edge[i]表示x->y这条边上的苹果树，用f[x][t-j-1]而不是f[x][t-j]是因为我们还要保留x->y这条边，最后01背包倒序枚举即可。

二叉苹果树代码

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn=110;

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

int head[maxn],Next[2*maxn],ver[2*maxn],edge[2*maxn],tot,u,v,z;

void add(int x,int y,int z){

	ver[++tot]=y;edge[tot]=z;Next[tot]=head[x];head[x]=tot;

}

void dp(int x,int fa){

	for(int i=head[x];i;i=Next[i]){

		int y=ver[i];

		if(y==fa) continue;

		dp(y,x);

		for(int t=q;t>=1;--t){

			for(int j=t-1;j>=0;--j){

				f[x][t]=max(f[x][t],f[x][t-j-1]+f[y][j]+edge[i]);

			}

		}

	}

}

int main(){

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

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

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

		add(u,v,z);

		add(v,u,z);

	}

	dp(1,0);

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

	return 0;

}

多叉苹果树代码

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn=330;

int n,q;

long long f[maxn][maxn];

int head[maxn],Next[2*maxn],ver[2*maxn],edge[2*maxn],tot,u,v,z;

void add(int x,int y,int z){

	ver[++tot]=y;edge[tot]=z;Next[tot]=head[x];head[x]=tot;

}

void dp(int x,int fa){

	for(int i=head[x];i;i=Next[i]){

		int y=ver[i];

		if(y==fa) continue;

		dp(y,x);

		for(int t=q;t>=1;--t){

			for(int j=t-1;j>=0;--j){

				f[x][t]=max(f[x][t],f[x][t-j-1]+f[y][j]+(long long)edge[i]);

			}

		}

	}

}

int main(){

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

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

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

		add(u,v,z);

		add(v,u,z);

	}

	dp(1,0);

	printf("%lld",f[1][q]);

	return 0;

}

巴特西

洛谷p2015二叉苹果树&yzoj1856多叉苹果树题解

f[x][[t]=max(f[x][t] , f[x][t-j-1] + f[y][j]+edge[i])

最新文章

热门文章