POJ 3342 - Party at Hali-Bula 树形DP+最优解唯一性判断

网友投稿 211 2022-11-06


POJ 3342 - Party at Hali-Bula 树形DP+最优解唯一性判断

好久没写树型dp了...以前都是先找到叶子节点.用队列维护来做的...这次学着vector动态数组+DFS回朔的方法..感觉思路更加的清晰...

关于题目的第一问...能邀请到的最多人数..so easy了...很基础的树形DP..dp[k][0]表示以k为根的子树不选k点时的最大人数...dp[k][1]代表选k点时的....

关键是题目要求判断是否最优解唯一...首先如果状态a可以转移到状态b并且状态a达到最优方案的方式不唯一....那么转移得到的b最优方案的方式也必然不唯一...那么可以用一个布尔型数组uni[k][tp] ( k代表哪个点,tp=0或者1..和dp里的意思一样...)来记录当前状态最优解是否唯一..转移的时候跟着转移...

如此一来..只要找到源头就可以了..设点p以及其父亲节点f

因为 dp[f][0] = dp[f][0] + max( dp[p][0] , dp[p][1] ) 并且f点若不使用,就不会再影响到更上层的点...所以若dp[p][0]==dp[p][1]..说明uni[f][0]=false..不唯一...

但是还要注意..最后的结果若dp[root][0]==dp[root][1]...就算uni[root][0]=true,unit[root][1]=true..方案也是不唯一的...这个很显然...

Program:

#include#include#include#include#include#include#include#include#include#define oo 1000000007#define ll long long#define pi acos(-1.0)#define MAXN 205using namespace std; map mymap;vector Tree[MAXN];int n,dp[MAXN][2]; bool uni[205][2];int ReadStringToInt(int &num){ char str[105]; string s; scanf("%s",str),s=str; if (!mymap.count(s)) mymap[s]=++num; return mymap[s];} void dfs(int x){ int i,m=Tree[x].size(); dp[x][0]=0,dp[x][1]=1; for (i=0;idp[p][0]) { dp[x][0]+=dp[p][1]; if (!uni[p][1]) uni[x][0]=false; }else if (dp[p][0]>dp[p][1]) { dp[x][0]+=dp[p][0]; if (!uni[p][0]) uni[x][0]=false; }else dp[x][0]+=dp[p][0],uni[x][0]=false; } if (dp[p][0]) { dp[x][1]+=dp[p][0]; if (!uni[p][0]) uni[x][1]=false; } } return;} int main(){ while (~scanf("%d",&n)) { int i,num; if (!n) break; for (i=1;i<=n;i++) Tree[i].clear(); mymap.clear(); num=0; ReadStringToInt(num); for (i=1;idp[1][1]) f=uni[1][0]; else f=uni[1][1]; if (f) printf("Yes\n"); else printf("No\n"); } return 0;}


版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：方法
上一篇:手机型号查询API（手机型号查询接口）
下一篇:HDOJ 3677 - Transportation 构图拆边,最小费用最大流
相关文章

 发表评论

暂时没有评论，来抢沙发吧~