这几天又感受到了被游戏$TreeDP$支配的恐惧,先写写初步对树形DP的认识吧。

首先,根据树形动规这个名字,就能知道这类题目是属于动态规划的范畴的,但是它们又有和普通动规完全不同的地方:在树上完成。

普通的动规一般都是在图上或者线性的,在图上,我们有向前和向后两个方向;线性动规中,我们有顺推和逆推两种思路;同样的,树上动规也对应的有两个方向:即从叶到根和从根到叶。和倒推和逆推类似。当然,具体问题具体分析,在不同的题目中,这两种方法有着不同的灵活的应用,没有高低之分。

之所以出现了这一类问题,是因为树本身就是一种非常毒瘤精彩的结构,它和图不同,自身就配备着“子树”,正好与DP中的“子问题”可以搭上边,都是从整体化成细小问题来解决的。

在树形动规中,也有几个比较难以实现的地方。

首先就是递归。

在树形动规中,平时繁杂的几重for循环变为了一层又一层看不透的递归,使用不熟练的话可能会有困难。

然后是细节多。

各种层出不穷的细节需要你用各种特判才能完美实现,如果脑子不清醒做起来就会非常恶心.

此外,就是所有动规题目共有的恶心之处,推动态转移方程式,这个没有捷径可走,只有通过多练习,找到手感之后才能略微提升自己刷DP题目的能力。


题目

洛谷P2015 二叉苹果树

大致题意:在一棵二叉树上求一条包含根节点且只包含q条边的道路并且使这条道路经过的边权总和最大。特殊条件:每个结点的儿子数量只会是0或2.

为什么一定包含根节点呢?因为这是一棵倒着长的数(雾)如果挖掉根节点,所有边都会消失。

所以考虑分成更小的子问题,从叶子结点向上扫,用$dp[i][j]$表示编号是$i$的结点为根时的字数在保留$j$条边时最大的权值和,然后扫一遍每个点都能够得到更新。

更新的过程中需要考虑。比如当前已经得到了$dp[i][j]$的值,往上推的时候就是$dp[父节点编号][j+1]+连接的权值$作为一个选择可能,与另外一个子树的相同情况打擂就ok。

还需要注意的一个坑点是,在选择中,不一定要选择根节点左子树或右子树的全部,可以两边各自选取一部分,只要边数和符合条件就可以更新。

$code:$

#include<bits/stdc++.h>
#define max(a,b) (a>b?a:b)
using namespace std;
struct node{int to,w;};
int n,q;
vector<node> g[110];
int dp[110][110];
void dfs(int u,int fa)
{
    int ls_id=-1,rs_id=-1;
    for(int i=0;i<g[u].size();i++)
    {
        if(g[u][i].to==fa)continue;
        if(ls_id!=-1)rs_id=i;
        else ls_id=i;
        dfs(g[u][i].to,u);
    }
    dp[u][0]=0;
    for(int i=1;i<=q;i++)
    {    
        if(ls_id!=-1)dp[u][i]=max(dp[u][i],dp[g[u][ls_id].to][i-1]+g[u][ls_id].w);
        if(rs_id!=-1)dp[u][i]=max(dp[u][i],dp[g[u][rs_id].to][i-1]+g[u][rs_id].w);
        if(rs_id!=-1&&ls_id!=-1)
            for(int j=1;j<i;j++)
                dp[u][i]=max(dp[u][i],dp[g[u][ls_id].to][j-1]+dp[g[u][rs_id].to][i-j-1]+g[u][ls_id].w+g[u][rs_id].w);
    }
        
}
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<n;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a].push_back((node){b,c});
        g[b].push_back((node){a,c});
    }
    dfs(1,0);
    cout<<dp[1][q]<<endl;
    return 0;
} 

洛谷P1272 重建道路

大致题意:在一棵有n个结点的树中,求至少需要割掉多少条边才能割出一个恰好有p个结点的树。

$dp[i][j]$表示以i为根的子树,保留j个节点,且当前子树不与父节点相连,需要拆掉的最小边数。

所以$dp[i][1]$的初始值就是i结点的入度。

转移方程$dp[u][j]=min{dp[u][j-k]+dp[v][k]-2}$,减二的原因是结点u在{u到v}和{v到u}两条边中都已经被割过了,所以需要减去二。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int n,p,ans=inf;
vector<int> g[200];
int dp[200][200];
void dfs(int u,int fa)
{
    for(int i=0;i<g[u].size();i++)
    {
        int v=g[u][i];
        if(v==fa)continue;
        dfs(v,u);
        for(int j=p;j>=1;j--)
            for(int k=1;k<j;k++)
                dp[u][j]=min(dp[u][j],dp[v][j-k]+dp[u][k]-2);
    }
}        
int main()
{
    scanf("%d%d",&n,&p);
    memset(dp,0x3f,sizeof(dp));
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
        dp[i][1]=g[i].size();
    dfs(1,0);
    for(int i=1;i<=n;i++)
        ans=min(ans,dp[i][p]);
    printf("%d\n",ans);
    return 0;
}

题目待更新...

最后修改:2020 年 04 月 10 日 06 : 16 PM