首页 > 代码库 > 【DP】树形DP 记忆化搜索

【DP】树形DP 记忆化搜索

2024-07-14 01:40:05   237人阅读

DP中的树形DP，解决方法往往是记忆化搜索。显然，树上递推是很困难的。当然做得时候还是得把状态定义和转移方程写出来：dp[u][1/0]表示以u为根节点的树 涂(1) 或 不涂(0) 颜色的最少方案数。树上DP有两个经典问法：一条边两端至少有个一个端点涂色，问整个tree最少涂色次数；还有一种忘了。。。此题是前种问法。
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=2000;int first[maxn],tot;int dp[maxn][3];int n,in[maxn];struct Edge{    int from,to,next;}E[maxn];void init(){    memset(first,-1,sizeof(first));    tot=0;    memset(dp,-1,sizeof(dp));    memset(in,0,sizeof(in));}void addedge(int u,int v){    E[tot].from=u;    E[tot].to=v;    E[tot].next=first[u];    first[u]=tot++;}int dfs(int u,bool flag){    if(flag){ if(dp[u][1]!=-1) return dp[u][1];}    else    { if(dp[u][0]!=-1) return dp[u][0];}    dp[u][1]=1;    dp[u][0]=0;    for(int e=first[u];e!=-1;e=E[e].next)    {        int v=E[e].to;        dp[u][1]+=min(dfs(v,true),dfs(v,false));        dp[u][0]+=dfs(v,true);    }    if(flag) return dp[u][1];    return dp[u][0];}int main(){    while(scanf("%d",&n)!=EOF)    {        init();        int node,num,a;        for(int i=0; i<n; i++)        {            scanf("%d:(%d)",&node,&num);            for(int i=0; i<num; i++)            {                   scanf("%d",&a);                in[a]++;                addedge(node,a);            }        }        int root;        for(int i=0;i<n;i++)            if(in[i]==0){root=i;break;}//        cout<<"root "<<root<<endl;        printf("%d\n",min(dfs(root,true),dfs(root,false)));//        for(int i=0;i<n;i++)//            cout<<dp[i][0]<<" "<<dp[i][1]<<endl;    }}


联系
我们