hdu2412（树形dp）-白红宇

hdu2412（树形dp）

阅读量：7099 次

发布时间：2019-06-28

本文共 2151 字，大约阅读时间需要 7 分钟。

题目链接：

题意：给定一棵关系树 , 从中选择一些点 , 使这些点均不存在亲子关系 , 最多能取多少个点 , 并且判断取法是否唯一 .

分析：如果这题没有判断唯一性，就和hdu1520一样了。设 dp[i][0] 为在以 i 为根的子树中 , 不选择点 i 最多能够选的数目 ,dp[i][1] 为选择 i 点的最多数目 .

状态转移方程 :

当 u 为叶子节点时 :

dp[u][0]=0;

dp[u][1]=1;

当 u 为非叶子节点时 :

dp[u][0]=sum(max(dp[v][0],dp[v][1])) (v 为 u 的儿子 )

dp[u][1]=sum(dp[v][0]) (v 为u 的儿子 )

至于判断唯一性：初始化flag数组全为1，即可行的唯一的。如果父节点以下的某一节点取时不唯一了，递归上去的结果也必定不唯一。

if(dp[v][0]>dp[v][1]&&flag[v][0]==0)flag[u][0]=0;//如果取子节点v即dp[v][0]时而flag[v][0]=0；由于dp[u][0]会取dp[v][0]使得flag[u][0]也变为0，即不唯一了

else if(dp[v][1]>dp[v][0]&&flag[v][1]==0)flag[u][0]=0;;//同理取dp[v][1]时而flag[v][1]=0；由于dp[u][0]会取dp[v][1]使得flag[u][0]也变为0，即不唯一了

else if(dp[v][0]==dp[v][1])flag[u][0]=0;//不唯一的源头

if(flag[v][0]==0)flag[u][1]=0;//由于dp[u][1]必取dp[v][0]，所以flag[v][0]为0的话，flag[u][1]也不唯一了。

#pragma comment(linker,"/STACK:102400000,102400000")#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 210#define FILL(a,b) (memset(a,b,sizeof(a)))using namespace std;struct edge{ int next,v; edge(){} edge(int v,int next):v(v),next(next){}}e[N*2];int head[N],tot;int num,n;int dp[N][2],flag[N][2];void addedge(int u,int v){ e[tot]=edge(v,head[u]); head[u]=tot++;}void dfs(int u,int fa){ dp[u][0]=0;dp[u][1]=1; flag[u][0]=flag[u][1]=1; for(int i=head[u];~i;i=e[i].next) { int v=e[i].v; if(v==fa)continue; dfs(v,u); dp[u][1]+=dp[v][0]; dp[u][0]+=max(dp[v][0],dp[v][1]); if(dp[v][0]>dp[v][1]&&flag[v][0]==0)flag[u][0]=0; else if(dp[v][1]>dp[v][0]&&flag[v][1]==0)flag[u][0]=0; else if(dp[v][0]==dp[v][1])flag[u][0]=0; if(flag[v][0]==0)flag[u][1]=0; }}char str[N],s1[N],s2[N];int main(){ while(scanf("%d",&n)&&n) { tot=0;num=0; map
                  
                   mp; FILL(head,-1); scanf("%s",str); mp[str]=++num; for(int i=1;i
                   
                    dp[1][0]&&flag[1][1]==1) printf("%d Yes\n",dp[1][1]); else if(dp[1][0]>dp[1][1]&&flag[1][0]==1) printf("%d Yes\n",dp[1][0]); else printf("%d No\n",max(dp[1][0],dp[1][1])); }}

View Code

转载于:https://www.cnblogs.com/lienus/p/4209680.html

你可能感兴趣的文章