[vijos1144]小胖守皇宫<树形dp>

题目链接：https://vijos.org/p/1144

woc我竟然A了，这道经典的树形dp或者说是树形dp的入门题我终于过了，虽然之前做过一些树形dp的题，但是这题开始还是一脸懵逼，dp方程如何定义都知道，但是不懂转移啊，这就有点伤了。。

dp方程定义dp[i][1]节点i 选自己

　　　　　dp[i][2]节点i选自己的儿子==不选自己和父亲

　　　　dp[i][3]节点i选自己的父亲==不选自己选父亲

然后就是转移了。。毕竟是基础题嘛，所以转移也不难

转移的时候我们是直接递归到叶节点然后再做前面的。。所以我们不用考虑父节点的状态

dp[i][1]选自己的时候，儿子节点就有两种方式，选儿子自己，或者选儿子的父亲dp[i][1]+=min(dp[son][1],dp[son][3]);

dp[i][2]选儿子时，儿子就选或不选两个方式，但是如果一旦所有的儿子都是不选了，我们就要找一个最小的儿子树的值在最后加上，

dp[i][2]+=min(dp[son][1],dp[son][2])如果全部选了2，就要在结尾加上dp[i][2]+=min(dp[son][1]-dp[son][2])

至于为啥加这个，就是这道题唯一有点思考难度的地方了，因为你是要加最小的儿子选一个的值，所以找到最小，比如时第s2个儿子，之前已经加了dp[s2][2]，所以最后的时候是加上dp[s2][1]-dp[s2][2]，相当于把之前的那个dp[s2][2]抵消了，就不会加重复

dp[i][3]选父亲时，因为我们是从子往父推，所以不从父亲转移，就考虑这时候的儿子节点，儿子节点来源就是儿子自己放和儿子的儿子放

dp[i][3]+=min(dp[son][1],dp[son][2]);

好吧这就是这道题的全部了，最后只需要输出根节点的选自己和选儿子方案的最小值就可，因为根没有父亲。。。

储存这个关系的方式有两种，一种是链表，一种是多叉树转二叉树，

两种方式的不同点在于链表是双向的，然后重新建树，默认1为根节点

而多叉树转二叉树是以题目给的关系建树，以没有父亲的点为根

链表：

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cstdlib>

 #include<cmath>

 #include<queue>

 #define maxn 1505

 using namespace std;

 int f[maxn][],n;

 struct edge{

     int u,v,w,nxt;

 }e[maxn*];

 int a[maxn],head[maxn],vis[maxn],tot;

 void adde(int u,int v){

     tot++;

     e[tot].u=u;e[tot].v=v;

     e[tot].nxt=head[u];

     head[u]=tot;

 }

 void work(int x){

     f[x][]=a[x];

     int s=0x3f3f3f,p=;

     for(int i=head[x];i!=-;i=e[i].nxt){

         int v=e[i].v;

         if(vis[v]==)continue;

         vis[v]=;

         work(v);

         f[x][]+=min(f[v][],f[v][]);

         if(f[v][]<f[v][]){

             f[x][]+=f[v][],p=;

         }else{

             f[x][]+=f[v][],s=min(s,f[v][]-f[v][]);

         }

         f[x][]+=min(f[v][],f[v][]);

     }

     if(p==)f[x][]+=s;

 }

 int main(){

     memset(head,-,sizeof(head));

     scanf("%d",&n);

     for(int i=;i<=n;i++){

         int num,val,sum;

         scanf("%d%d%d",&num,&val,&sum);

         a[num]=val;

         for(int j=;j<=sum;j++){

             int b;

             scanf("%d",&b);

             adde(num,b);adde(b,num);

         }

     }

     vis[]=;work();

     printf("%d",min(f[][],f[][]));

 }

多叉树转二叉树

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cstdlib>

 #include<cmath>

 #include<queue>

 #define maxn 3005

 using namespace std;

 int n,m,a[maxn],root;

 int f[maxn][],vis[maxn];

 int lson[maxn],rson[maxn],fa[maxn];

 void work(int x)

 {

     f[x][]=a[x];

     int s=0x3f3f3f,p=;

     for(int i=lson[x];i!=;i=rson[i]){

         work(i);

         if(f[i][]<f[i][]){

             f[x][]+=f[i][];s=min(f[i][]-f[i][],s);

         }else f[x][]+=f[i][],p=;

         f[x][]+=min(f[i][],f[i][]);

         f[x][]+=min(f[i][],f[i][]);

     }

     if(p==)f[x][]+=s;

 }

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<=n;i++){

         int num,val,q;

         scanf("%d%d%d",&num,&val,&q);

         a[num]=val;

         for(int j=;j<=q;j++){

             int s,now=lson[num];

             scanf("%d",&s);

             fa[s]=num;

             if(j==)lson[num]=s;

             else {

                 while(rson[now]!=){

                     now=rson[now];

                 }

                 rson[now]=s;

             }

         }

     }

     for(int i=;i<=n;i++)

      if(fa[i]==)work(i),root=i;

     printf("%d",min(f[root][],f[root][]));

 }

提醒一点，多叉树转二叉树需要在执行dp之前跑个O（n）找到根节点

巴特西

[vijos1144]小胖守皇宫<树形dp>

最新文章

热门文章