前言

​    学OI的时候就做过树形dp的题,不过那时候全在划水。看了看题解还不太懂就直接照着题解写了,现在再回来看还是不会QAQ,所以就再看看然后自己写了一遍。


A. 没有上司的舞会

题意

​    有 $N$ 个职员被邀请去参加公司的舞会,他们每个人对应着一个快乐指数 $h_i$ ,如果该职员来了就会为舞会增加$h_i$ 点快乐指数。这 $N$ 个职员之间有从属关系,也就是说他们的关系就像一棵以顶级上司为根的树,父结点就是子结点的直接上司。如果一个职员的直接上司来到了舞会,那么他本人就不会再来。问邀请哪些职员可获得最大的快乐指数,最大为多少。

思路

​    职员之间的关系是以树的形式给出的,所以先用链式前向星来存储数。存的时候我们用vis数组记录一下如何那个人有上司,就将他标记一下,最终没有标记的就是没有上司的,也就是顶级上司,也就是我们的根节点root。
​    树形dp,顾名思义,在树上进行dp,通过递归dfs,先算出子树的状态,再通过递归的回溯来合并。那么我们考虑一下设计状态,很明显一个人的状态有来和不来,两个情况。所以我们设计状态 $dp[i][0/1]$ 来表示职员 i 来或者不来,我们用u来表示当前节点,用v来表示当前节点的子节点,那么状态转移如下:

  • $dp[u][0]=max(dp[v][0],dp[v][1]) $ (上司u没有来,那么下属v可以来,也可以不来,选一个大的策略)
  • $dp[u][1]=dp[v][0]+h[u]$ (上司u来了,下属v肯定不来)

​    最终的答案就是 $max(dp[root][0],dp[root][1])$ ,上司来和不来两种策略中的最大一种。

代码实现

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>

using namespace std;

const int maxn=6005;
int head[maxn];
struct edge
{
    int next;
    int to;
}e[maxn];
int cnt,n,l,k,vis[maxn],root;
int r[maxn];
int dp[maxn][2];
void add(int l,int k)
{
    e[++cnt].next=head[l];
    e[cnt].to=k;
    head[l]=cnt;
}
void dfs(int u)
{
    dp[u][0]=0;
    dp[u][1]=r[u];
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        dfs(v);
        dp[u][1]+=dp[v][0];
        dp[u][0]+=max(dp[v][1],dp[v][0]);
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&r[i]);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&l,&k);
        add(k,l);
        vis[l]++;
    }
    scanf("%d%d",&l,&k);
    for(int i=1;i<=n;i++) 
    { 
        if(!vis[i]) root=i;
    }
    dfs(root);
    printf("%d",max(dp[root][0],dp[root][1]));
    return 0;
} 


B. 战略游戏

题意

​    小姜老师要建立一个树,树节点两两之间通过道路连接,他要在这些节点上放一些小人,每个小人可监管与该节点相连的道路,问最少放置多少小人可以监管所有道路。(数据保证0为根节点)

思路

​    这个题跟上个题有点像,首先我们也是用链式前向星把树给存下来,不过这个题的输入跟上道题有点不一样,本质都是一样的。因为我们只需要dfs下去,然后向上回溯的时候合并,所以只需要存单向边即可。
​    对于一个节点我们也是有两种策略,选或者不选,那么我们也可以把状态写成 $dp[i][1/0]$ ,对应着 i 这个节点选或者不选,我们把当前节点看作u,子节点看作v,状态转移如下:

  • $dp[u][1]+=\Sigma (dp[v][0],dp[v][1]) +1$ (u选了,v选不选都可以,加上自身的1)
  • $dp[u][0]+=\Sigma dp[v][1]$ (如果u没有选,那么v一定要选,才能监管到u的道路)

​    很显然这个答案是 $min(dp[0][0],dp[0][1])$

代码实现

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>

using namespace std;

const int maxn=1505;
struct edge
{
    int next,to;
}e[maxn];
int u,v;
int head[maxn];
int dp[maxn][2];
int num;
int n,cnt;
void add(int u,int v)
{
    e[++cnt].next=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}
void dfs(int u)
{
    dp[u][1]=1;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        dfs(v);
        dp[u][1]+=min(dp[v][1],dp[v][0]);
        dp[u][0]+=dp[v][1];
    } 
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&u,&num);
        for(int i=1;i<=num;i++)
        {
            scanf("%d",&v);
            add(u,v);
        }
    }
    dfs(0);
    printf("%d",min(dp[0][0],dp[0][1]));
    return 0;
}


C. 二叉苹果树

题意

​    有一颗二叉苹果树,也就是说树枝如果分叉,一定是分二叉。苹果树有 $n$ 个节点,树根编号为 1 。每个树枝上都有一定数量的苹果,如果最终保留 $q$ 根树枝,问最多能够保留多少苹果。

思路

​    这个树形dp要比上面的还要难一些,因为我们的状态不能够只考虑是否保留当前的树枝了,因为保留当前树枝也会有很多种关于保留子树枝选择。看了题解大佬的说法是,可以定义成 $f[u][j]$ 来表示 u 的子树上保留 j 条边时所能获得最大的苹果数。所以我们考虑一下转移方程,首先我们能保留的最大边数是当前子树所具有的所有树枝,对于一个节点下的两个树枝,我们可以选择取,或者不取,那么这就类似于一个背包问题,对于一定的容量(一定量的树枝),我们取几个树枝才能获得最大的价值。但是我们注意,对于一个节点u,我们如果要取他的节点v,那么我们u-v之间这个树枝一定要保留,不然会不能取得v,这是一个隐藏的条件。
​    因此转移方程: $dp[u][i]=max(dp[u][i],dp[u][i-j-1]+dp[v][j]+w[u][v] $ ,$w[u][v]$为当前u-v树枝的苹果数。代码里面因为我懒得计算子树的树枝数了,所以就直接从最大的q来枚举了,就没考虑那么多,可能复杂度稍微高一点,但是高不到哪去其实QAQ...

代码实现

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>

using namespace std;

const int maxn=105;
struct edge
{
    int next,to,w;
}e[maxn];
int n,cnt,q;
int u,v,w;
int dp[maxn][maxn];
int head[maxn];
void add(int u,int v,int w)
{
    e[++cnt].next=head[u];
    e[cnt].to=v;
    e[cnt].w=w;
    head[u]=cnt;
}

void dfs(int u)
{
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        dfs(v);
        for(int j=q;j>=0;j--)
        {
            for(int k=0;k<=j-1;k++)
            {
                dp[u][j]=max(dp[u][j],dp[u][j-1-k]+dp[v][k]+e[i].w);
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }
    dfs(1);
    printf("%d",dp[1][q]);
    return 0;
}
最后修改:2020 年 08 月 18 日 01 : 05 AM
如果觉得我的文章对你有用,请随意赞赏