大佬教程收集整理的这篇文章主要介绍了编译 (树形DP),大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
编译器
【问题描述】
CCF是信奥班的成员,因为喜欢玩Android系统而出名。
CCF写出了一个伟大的C++工程,一共包含N个源文件。在CCF的脑海中,N个源文件构成一个树形结构。每一个源文件是树上的一个节点,其中1号节点是树根。
现在,CCF开始编译这个工程。每次他会从树上选择一条链(包含两个端点)迚行编译。由于编译器的特性,要求这条链的一个端点必须是另一个端点的祖先。一条链可以退化成一个点。每个源文件都需要被编译恰好一次。
每一个源文件都有一个两位十六迚制数的标志值(范围从00到ff)。对于每一条选择的链,把该上面所有源文件的标志值异或起来,得到这条链的特征值。把所有选择的链的特征值相加,得到这次编译的代价。
现在CCF想知道 ==至少选择几条链才能编译所有文件== 。==在选择的链数目最小的时候,编译的代价最小是多少==。
【输入格式】
第一行一个整数N。
以下一行,N个两位十六迚制数,表示第1号源文件到第N号源文件的特征值。(十六迚制数中的字母采取小写,不足两位的在前面补零。亦即C/C++中使用”%02x”输出的格式。)
以下(N - 1)行,每行两个整数,给出树上的一条边所连接的两个顶点。
【输出格式】
一行两个整数。依次为,选择的链的最小数目、编译的最小代价。两个数均以十迚制形式输出。
【样例输入1】
【样例输出1】
【样例输出2】
说明:最优方案为(1,(2,4),(5)或(1,5),(4)。
【数据范围】
0 ≤ N ≤ 20,000。
分析:此题包含了两个问题:1.选择的链最小数目 2.选择的链最少的情况下,编译的最小代价。
#include<cstdio> #include<cString> #include<iostream> using namespace std; struct node{ int u; int v; int next; }; bool fl[20050] = {0}; //由于建的是无向图,所以遍历时标记父亲节点,避免找儿子时误找到父亲 node edge[40050]; //记录边 int tot = -1,first[20050],w[20050],minn[20050],dp[20050][270]; // minn 当前节点为根的子树异或总和的最小值 // dp[u][j] 以点u为根节点,当子树异或值为j时,该子树异或总和的最小值 // minn[u] = min{minn[u],dp[u][j] + j} // dp[u][j ^ w[u]] = min{minn[Vi]总和 - minn[Vj] + dp[vj][j]} void add(int u,int v){//建边 edge[++tot].u = u; edge[tot].v = v; edge[tot].next = first[u]; first[u] = tot; } void BACk(int x,int sum){//找完叶子结点后回溯时计算dp和minn minn[x] = 0x7f7f7f7f; for(int i=0;i<=255;i++){ for(int j=first[x];j!=-1;j = edge[j].next){ if(!fl[edge[j].v])dp[x][i ^ w[x]] = min(dp[x][i ^ w[x]],sum - minn[edge[j].v] + dp[edge[j].v][i]); } } for(int i=0;i<=255;i++) minn[x] = min(minn[x],dp[x][i] + i); } int ans = 0; void find(int X){//找叶子节点 bool leaf = 1;//是否是叶子结点的标记 int sum = 0;//所有儿子的minn之和,在计算当前节点的minn和 dp时要用 fl[x] = true; for(int i=first[x];i!=-1;i = edge[i].next){ if(fl[edge[i].v]) conTinue; leaf = 0; find(edge[i].v); sum += minn[edge[i].v]; } fl[x] = false;//将fl还原,以便BACk函数中判断儿子 if(leaf){ ans++; minn[x] = w[x]; dp[x][w[x]] = 0; } else BACk(x,sum); } int main(){ freopen("compiler.in","r",stdin); freopen("compiler.out","w",stdout); memset(first,-1,sizeof(first)); memset(dp,0x3f,sizeof(dp)); int u,v,n;scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%02x",&w[i]); for(int i=1;i<n;i++){ scanf("%d%d",&u,&v); //输入不一定是父亲 儿子的顺序,所以建无向图,双向的边 add(u,v); add(v,u); } ans = 0; find(1); printf("%d ",ans); printf("%d",minn[1]); return 0; }
以上是大佬教程为你收集整理的编译 (树形DP)全部内容,希望文章能够帮你解决编译 (树形DP)所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。