menu Stephen Space
more_vert
chevron_right 首页 » 【OI】 » 正文
【OI】OI日记 · 8月4号——树形DP
2020-08-04 | 【OI】 | 暂无评论 | 34 次阅读 | 272字

    今天是学习DP的第二天,我的天哪,简直要S了。废话不多说,今天学习的是树形DP。树形DP,顾名思义,就是在一颗树上做DP(啥?在树上做DP?不怕摔死???
    好了,不闹了。做树形DP一般都要用DFS来扫描树,然后从底部叶子开始,在回溯到根的过程中进行DP。大体思路根填表法类似,只不过是在树上进行的。所以,它的大体程序长这样:


void dp_tree(int point,int fa)
{
    for (int i=0;i<=tree.size();i++)
    {
        int nxt=tree[point][i];
        if (vis[nxt]) return
        dp_tree(nxt,point);
        # DP Code #
    }
 } 

当然,老样子,有其它条件可以自己增加维度。
    如果是刚刚开始学习,建议先做做下面两道题,都很经典:

如果已经有一定水平,可以去看看这道题:

我这里把这道题的代码放出来,还是挺长的,毕竟是道蓝题。

#include<bits/stdc++.h>
#define MAXN 1005
using namespace std;
int pnt[MAXN],nextx[MAXN*MAXN],v[MAXN*MAXN];
int f[MAXN][5];
int n,m;
int x,tot;
void init()
{
    memset(pnt,-1,sizeof(pnt));
    memset(nextx,-1,sizeof(nextx));
    tot=-1;
}
void edge(int x,int y)
{
    tot++;nextx[tot]=pnt[x];pnt[x]=tot;v[tot]=y;
    tot++;nextx[tot]=pnt[y];pnt[y]=tot;v[tot]=x;
}
void dp(int x,int fa)
{
    int ans1=INT_MAX;
    int ans2=INT_MAX;
    if(nextx[pnt[x]]==-1&&x!=1)
    {
        f[x][0]=1;
        f[x][1]=1;
        f[x][2]=1;
        f[x][3]=0;
        f[x][4]=0;
        return;
    }
    for(int i=pnt[x];i!=-1;i=nextx[i])
    if(v[i]!=fa) dp(v[i],x);
    for(int i=pnt[x];i!=-1;i=nextx[i])
    {
        if(v[i]==fa) continue;
        f[x][2]+=f[v[i]][4];
        f[x][3]+=f[v[i]][0];
        f[x][4]+=f[v[i]][3];
        ans1=min(ans1,f[v[i]][2]-f[v[i]][3]);
        ans2=min(ans2,f[v[i]][1]-f[v[i]][0]);
    }
    f[x][0]=f[x][3]+ans2;
    f[x][1]=f[x][4]+ans1;
    f[x][2]++;
    f[x][3]=min(min(f[x][3],f[x][2]),min(f[x][1],f[x][0]));
    f[x][4]=min(min(f[x][0],min(f[x][4],f[x][3])),min(f[x][2],f[x][1]));
    f[x][0]=min(f[x][0],min(f[x][1],f[x][2])); 
    f[x][1]=min(f[x][1],f[x][2]);
}

int main()
{
    cin>>n;
    init();
    for(int i=1;i<n;++i)
    {
        cin>>x;
        edge(i+1,x);
    }
    dp(1,0);
    cout<<f[1][0]<<endl;
    return 0;
}

    当然,做完题后写解题记录也是一个好习惯。所以,我决定每天解题记录打卡!这是今天的:

    好,今天的日记就到这里,我们明天见!!!

None
发表评论
暂无评论
textsms
account_circle
email
link