树形DP-白红宇

树形DP

阅读量：4695 次

发布时间：2019-06-09

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

树形DP小结：

1：n个点，n-1条边；

2：无环，根结点可由子结点推出；

3：一般的状态都是以某一个结点为根的子树代表什么，

然后通过递归，由一个一个子结点推出根结点状态；

递推关系：Dp[i][j]=max(dp[i][j],dp[i][k]+dp[son[i][j-k]);

说明递推的含义，首先dp[i][j]的第一个值肯定从dp[son[i]][k]来，当换另一个son2[i]，dp[i][j]就是由俩个son推出，其他son同理；

4：对于一棵树，可以随意选一个点为根，开一个vis[]数组，记录该结点是否访问过；

最裸的树形DP，定义dp[i][0]表示以i为根的子树不选i能邀请到的最大值；

Dp[i][1]表示以i为根的子树选i能邀请到的最大值；

状态转移：dp[i][0]+=max(dp[son][0],dp[son][1]); dp[i][1]+=dp[son][0];

注意每个点的值有正有负；

View Code

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 using namespace std; 9 const int MAXN=6010;10 int dp[MAXN][2];11 const int INF=1000000; 12 vector 
             
               g[MAXN];13 int c[MAXN];14 int n;15 int v[MAXN]; 16 void TREEDP(int root)17 {18 int d=g[root].size();19 if (d==0) {20 dp[root][1]=c[root];21 dp[root][0]=0;22 return ; 23 } 24 for (int i=0;i
              
               0) 35 dp[root][1]+=dp[c][0]; 36 } 37 dp[root][0]=-INF;38 for (int i=0;i
               
                0 && dp[root][0]<0)43 {44 dp[root][0]=t;45 } else if (t<0 && dp[root][0]<0)46 {47 if (dp[root][0]
                
                 0 && dp[root][0]>=0)49 {50 dp[root][0]+=t; 51 } 52 } 53 } 54 int main()55 {56 // freopen("D:\in.txt","r",stdin); 57 while (~scanf("%d",&n))58 {59 for (int i=1;i<=n;i++)60 {61 scanf("%d",&c[i]); 62 g[i].clear(); 63 } 64 int u,v;65 bool vis[MAXN];66 memset(vis,0,sizeof(vis)); 67 while (~scanf("%d%d",&u,&v)) 68 {69 if (u==0 && v==0) break; 70 g[v].push_back(u); 71 vis[u]=1; 72 } 73 memset(dp,0,sizeof(dp)); 74 75 for (int i=1;i<=n;i++)76 {77 if (vis[i]==0)78 {79 TREEDP(i);80 cout<
                 
                  <

和上一题基本一样，但还要询问方案是否唯一；加一个数组记录当前状态是否唯一如果不唯一，当根结点的状态有它推出时，根结点的状态也就不唯一

//程序统一输出的方式，不要cout和printf混用，俩着输出性质不一样；

View Code

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
            7 #include
            
              8 #include
             
               9 using namespace std; 10 const int MAXN=210; 11 map
              
                mp; 12 int sz; 13 vector 
               
                g[MAXN]; 14 int dp[MAXN][2]; 15 int dug[MAXN][2]; 16 int vis[MAXN]; 17 int n; 18 void init() 19 { 20 sz=0; 21 mp.clear(); 22 for (int i=0;i
                
                 dp[c][0] && dug[c][1]==0) 51 { 52 dug[rt][0]=0; 53 } else 54 if (dp[c][1]
                 
                  >n) 76 { 77 if (n==0) break; 78 init(); 79 cin>>s; 80 mp_find(s); 81 for (int i=0;i
                  
                   >s1>>s2; 84 int u=mp_find(s1); 85 int v=mp_find(s2); 86 g[v].push_back(u); 87 } 88 89 TREEDP(0); 90 91 if (dp[0][1]>dp[0][0]) 92 { 93 if(dug[0][1]) cout<
                   
                    <<" Yes"<

很裸的树形DP，先一遍dfs，统计出以每个结点为根的子树包含的队伍，和该子树以该子树跟为聚集地所走的路径，这样就算出了以根结点为聚集地需要的总路程；

再一遍 dfs，由总根结点推到子结点，记录下最小值。

//对于数据大的，但有感觉没有超，还是果断用long long ,有可能中间计算超了；

//该题用dfs递归会爆栈，要手写stack，或用C++交可以用爆栈外挂，

#pragma comment(linker, "/STACK:1024000000,1024000000")

View Code

1 #pragma comment(linker, "/STACK:1024000000,1024000000")  2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
             7 #include
           
             8 #include
            
              9 using namespace std; 10 const int N=100100; 11 typedef __int64 ll; 12 ll dp[N]; 13 ll dug[N]; 14 int n; 15 ll c[N],vis[N]; 16 ll ans; 17 struct node 18 { 19 int v,w; 20 }; 21 vector 
             
               g[N]; 22 void TREEDP(int rt) 23 { 24 vis[rt]=1; 25 int d=g[rt].size(); 26 if (d==0) 27 { 28 dp[rt]=c[rt]; 29 dug[rt]=0; 30 return; 31 } 32 dp[rt]=c[rt]; 33 dug[rt]=0; 34 for (int i=0;i

求树上离一个点最远的距离；我是先一遍dfs记录下以该点为根的子树的子结点到根的最远距离，然后转移总根结点，求出每个结点的ans；同上类似；

View Code

1       2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
             7 #include
           
             8 #include
            
              9 using namespace std; 10 typedef long long ll; 11 const int N=10010; 12 ll dp[N]; 13 struct node 14 { 15 int v,w; 16 }; 17 vector
             
               g[N]; 18 int vis[N]; 19 ll c[N]; 20 int n; 21 void init() 22 { 23 for (int i=1;i<=n;i++) 24 g[i].clear(); 25 memset(dp,0,sizeof(dp)); 26 memset(vis,0,sizeof(vis)); 27 } 28 void TREEDP(int rt) 29 { 30 vis[rt]=1; 31 int d=g[rt].size(); 32 if (d==0) 33 { 34 dp[rt]=0; 35 return; 36 } 37 for (int i=0;i

二分+树形DP；

据说凡是求最大最小值或最小最大值都可以二分确定一个因素，然后验证；

二分上限，树形DP求不超上界切断联络的最小代价；

View Code

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 using namespace std; 9 const int N=1010; 10 int dp[N]; 11 int n,all; 12 int vis[N]; 13 bool bo[N]; 14 struct node 15 { 16 int v,w; 17 }; 18 vector
             
               g[N]; 19 20 const int INF=1000000000; 21 void TREEDP(int rt,int c,int m) 22 { 23 vis[rt]=1; 24 int d=g[rt].size(); 25 26 int t=0; 27 int flag=0; 28 for (int i=0;i
              
               l)102 {103 int m=(l+r)/2;104 if (solve(m))105 {106 ans=m;107 r=m;108 }else l=m+1;109 }110 printf("%d\n",ans);111 112 113 }114 return 0;115 }

dp[i][j]表示以i为根，攻下j个城市的最大获得；

dp[i][j]=max(dp[i][j[,dp[son][k]+dp[i][j-k]);类似于在树上做分组背包；

View Code

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 using namespace std; 9 const int MAXN=210;10 int n,m;11 vector
             
               g[MAXN];12 int dp[MAXN][MAXN]; 13 //dp[i][j] ,表示以i为根，攻下j个城市的最大获得； 14 int c[MAXN]; 15 void init()16 {17 memset(dp,0,sizeof(dp));18 for (int i=0;i<=n;i++)19 {20 g[i].clear(); 21 } 22 23 } 24 void TREEDP(int rt,int m)25 {26 27 int d=g[rt].size(); 28 dp[rt][1]=c[rt]; 29 for (int i=0;i
              
               1) 34 TREEDP(c,m-1);35 for (int j=m;j>0;j--)36 {37 int v=j+1;38 for (int k=1;k

同上;注意特判；

View Code

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 using namespace std; 9 10 const int MAXN=110;11 int n,m;12 vector
             
               g[MAXN];13 int c[MAXN],w[MAXN];14 int dp[MAXN][MAXN];15 int vis[MAXN]; 16 //dp[i][j] 以i为根花费j能获得的最大利益； 17 18 void TREEDP(int rt)19 {20 21 vis[rt]=1;22 int d=g[rt].size(); 23 for (int i=c[rt];i<=m;i++) dp[rt][i]=w[rt]; 24 for (int i=0;i
              
               =c[rt];j--)32 {33 34 for (int k=1;j+k<=m;k++)35 {36 if (dp[son][k])37 dp[rt][j+k]=max(dp[rt][j+k],dp[rt][j]+dp[son][k]); 38 39 } 40 } 41 } 42 43 } 44 } 45 void init()46 {47 memset(dp,0,sizeof(dp));48 for (int i=0;i<=n;i++) g[i].clear();49 memset(vis,0,sizeof(vis)); 50 } 51 int main()52 {53 //freopen("D:\in.txt","r",stdin); 54 while (~scanf("%d%d",&n,&m)) 55 {56 if (n==-1 && m==-1) break; 57 init(); 58 for (int i=1;i<=n;i++)59 {60 int a,b;61 scanf("%d%d",&a,&b);62 c[i]=(a+19)/20;63 // if (a%20) c[i]+=1;64 w[i]=b; 65 } 66 for (int i=0;i

题意差不多，但要特别处理0的情况；

View Code

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 using namespace std; 9 const int N=10010;10 int dp[N][11];11 int n,s,num;12 int vis[N];13 struct node14 {15 int v,w;16 };17 vector
             
               g[N];18 const int INF=1000000000;19 20 21 void TREEDP(int rt)22 {23 vis[rt]=1;24 int d=g[rt].size();25 for (int i=0;i
              
               =0;j--)32 {33 int t=INF;34 for (int k=0;k<=j;k++)35 {36 37 if (j-k==0)38 t=min(t,dp[rt][k]+dp[v][j-k]+w*2);39 else t=min(t,dp[rt][k]+dp[v][j-k]+w*(j-k));40 41 }42 dp[rt][j]=t;43 }44 }45 46 }47 void init()48 {49 memset(dp,0,sizeof(dp));50 memset(vis,0,sizeof(vis));51 for (int i=0;i<=n;i++) g[i].clear();52 53 }54 int main()55 {56 //freopen("D:\in.txt","r",stdin);57 while (~scanf("%d%d%d",&n,&s,&num))58 {59 init();60 for (int i=0;i

这题主要还是缩点；树形DP，就随便搞一下；

View Code

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
             using namespace std;const int M=20005;const int N=10005;const int INF=1000000000; struct node{ int u,v; int next; }edge[M*2],edge1[M*2];int head[N],tol,cnt,dfn[N],low[N],vis[N],belong[N];int toll,head1[N],val[N],val1[N]; int n,m,SUM,Min,scc;stack
            
              S; void insert(int a,int b){ node v={a,b,head[a]}; edge[tol]=v; head[a]=tol++; } void insert1(int a,int b){ node v={a,b,head1[a]}; edge1[toll]=v; head1[a]=toll++; } void tarjan(int u,int father){ int j,v,flag; dfn[u]=low[u]=cnt++; vis[u]=1; S.push(u); flag=0; for (j=head[u];j!=-1;j=edge[j].next) { v=edge[j].v; if (v==father && !flag) { flag=1;continue; } if (!vis[v]) tarjan(v,u); low[u]=min(low[u],low[v]); } if (dfn[u]==low[u]) { scc++; do { v=S.top();S.pop(); belong[v]=scc; val[scc]+=val1[v]; } while (v!=u) ; } } int dfs(int u,int father){ int j,v,sum; sum=val[u]; for (j=head1[u];j!=-1;j=edge1[j].next) { v=edge1[j].v; if (v==father) continue; sum+=dfs(v,u); } Min=min(Min,abs(SUM-2*sum)) ; return sum; } int main(){ while (~scanf("%d%d",&n,&m)) { memset(head,-1,sizeof(head)); tol=cnt=0; SUM=0; for (int i=0;i

转载于:https://www.cnblogs.com/Rlemon/archive/2012/08/04/2622493.html

你可能感兴趣的文章