本文主要是介绍【bzoj1369】【Baltic2003】【Gem】【树形dp】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Description
给出一棵树，要求你为树上的结点标上权值，权值可以是任意的正整数 唯一的限制条件是相临的两个结点不能标上相同的权值，要求一种方案，使得整棵树的总价值最小。
Input
先给出一个数字N,代表树上有N个点,N<=10000 下面N-1行,代表两个点相连
Output
最小的总权值
Sample Input
10
7 5
1 2
1 7
8 9
4 1
9 7
5 6
10 2
9 3
7 5
1 2
1 7
8 9
4 1
9 7
5 6
10 2
9 3
Sample Output
14
题解：
一共需要的颜色不超过logn个.
设f[i][j]表示i这棵子树,根节点的颜色是j的最小代价.
dp即可.
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 10010
using namespace std;
int point[N],next[N<<1],n,cnt,v[N],x,y,f[N][20],ans;
struct use{int st,en;}e[N<<1];
void add(int x,int y){next[++cnt]=point[x];point[x]=cnt;e[cnt].st=x;e[cnt].en=y;
}
void dp(int x,int fa){for (int i=point[x];i;i=next[i])if (e[i].en!=fa){dp(e[i].en,x);for(int j=1;j<=14;j++){int mn=1000000;for (int k=1;k<=14;k++)if (k!=j) mn=min(mn,f[e[i].en][k]);f[x][j]+=mn;}}for (int i=1;i<=14;i++) f[x][i]+=i;
}
int main(){scanf("%d",&n);for (int i=1;i<n;i++){scanf("%d%d",&x,&y);add(x,y);add(y,x);}dp(1,0);ans=1000000;for (int i=1;i<=14;i++) ans=min(ans,f[1][i]);cout<<ans<<endl;
} 这篇关于【bzoj1369】【Baltic2003】【Gem】【树形dp】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
