树形DP

树形dp的模板是在做题中总结出来的

POJ 2342 Anniversary party_边

树形DP满足自下而上，在dfs处通过递归实现
与scnuoj不一样，这题需要找根节点

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define maxi 6010
using namespace std;
int n,dp[maxi][2],book[maxi];
vector<int>  G[maxi];

void dfs(int u){
    for(int i=0;i<G[u].size();i++){
        int to=G[u][i];
        dfs(to);
        dp[u][1]+=dp[to][0];
        dp[u][0]+=max(dp[to][0],dp[to][1]);
    }

}


int main()
{
    freopen("data.txt","r",stdin);
    cin>>n;
    int a,b;
    for(int i=1;i<=n;i++){
        cin>>dp[i][1];
    }
    for(int i=1;i<n;i++){
        cin>>a>>b;
        G[b].push_back(a);
        book[a]=1;//寻找根节点
    }
    cin>>a>>b;
    int root;
    for(int i=1;i<=n;i++){
        if(!book[i]){
            root=i;
            break;
        }
    }

    dfs(root);
    cout<<max(dp[root][0],dp[root][1]);
    return 0;
}

 

洛谷 P2016 战略游戏_边

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define maxi 6010
using namespace std;
int n,dp[maxi][2],book[maxi];
vector<int>  G[maxi];

void dfs(int u){
    dp[u][1]=1;
    for(int i=0;i<G[u].size();i++){
        int to=G[u][i];
        dfs(to);
        dp[u][0]+=dp[to][1];
        dp[u][1]+=min(dp[to][0],dp[to][1]);
    }
}


int main()
{
    freopen("data.txt","r",stdin);
    cin>>n;
    int a,b,c;
    int root;
    for(int i=1;i<=n;i++){
        cin>>a>>b;

        for(int j=0;j<b;j++){
            cin>>c;
            G[a].push_back(c);
            book[c]=1;
        }
    }
    //i从0开始，自行看题
    for(int i=0;i<n;i++){
        if(!book[i]){
            root=i;
            break;
        }
    }

    dfs(root);
    cout<<min(dp[root][0],dp[root][1]);
    return 0;
}

 

POJ 3659 Cell Phone Network_结点

//#include <bits/stdc++.h>
#define maxi 100010 
#define INF 99999999
using namespace std;
//dp[i][0] 自己不选，选父亲
//dp[i][1] 自己不选，选儿子
//dp[i][2] 选自己 
vector<int> G[maxi];
int dp[maxi][3];

void dfs(int u,int f){
    dp[u][0]=0;
    dp[u][1]=0;
    dp[u][2]=1;
    if(G[u].size()==1&&G[u][0]==f){
        //到底了 
        dp[u][1]=INF;
        return ;
    }
    int flag=0,minn=INF,son=0,v;
    for(int i=0;i<G[u].size();i++){
        v=G[u][i];
        //如果是最后一个结点，则不算 
        if(v==f)
            continue;
        dfs(v,u);
        //u是自己，v是子节点 
        dp[u][2]+=min(dp[v][0],min(dp[v][1],dp[v][2]));
        dp[u][0]+=min(dp[v][1],dp[v][2]); 
        if(dp[v][1]<dp[v][2]){
            dp[u][1]+=dp[v][1];
            if(minn>dp[v][2]){
                minn=dp[v][2];
                son=dp[v][1];
            }
        }
        else{
            flag=1;
            dp[u][1]+=dp[v][2];
        }
    }
    if(!flag)
        dp[u][1]+=minn-son; 
} 

int main(){
    int n;
    cin>>n;
    int a,b;
    for(int i=1;i<n;i++){
        cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs(1,-1);
    cout<<min(dp[1][1],dp[1][2])<<endl;
    return 0;
}

 

ZOJ 3201 Tree of Tree_树上DP

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
//#include <bits/stdc++.h>
#define maxi 110 
#define INF 99999999
using namespace std;

vector<int> G[maxi];
int dp[maxi][maxi],w[maxi],k,vis[maxi];

void dfs(int u,int f){
    dp[u][1]=w[u];
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        //如果是最后一个结点，则不算 
        if(v==f)
            continue;
        dfs(v,u);
        //u是自己，v是子节点 
        for(int j=k;j>=1;j--)
            for(int l=1;l<=j;l++)
                dp[u][j]=max(dp[u][j],dp[u][l]+dp[v][j-l]);
    }
} 

int main(){
//  freopen("data","r",stdin);
    int n;
    while(scanf("%d%d",&n,&k)!=EOF){
        memset(dp,0,sizeof(dp));
        for(int i=0;i<n;i++){
            G[i].clear();
            cin>>w[i];  
        }
        int a,b;
        for(int i=0;i<n-1;i++){
            cin>>a>>b;
            G[a].push_back(b);
            G[b].push_back(a);
        }

        dfs(0,-1);
        int res=0;
        for(int i=0;i<n;i++)
            res=max(dp[i][k],res);
        cout<<res<<endl;    
    }
    return 0;
}

 

洛谷 P2014 选课_线上DP

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
//#include <bits/stdc++.h>
#define maxi 350 
#define INF 99999999
using namespace std;

vector<int> G[maxi];
int dp[maxi][maxi],k,n,m,w[maxi];

void dfs(int u){
    for(int i=1;i<m;i++)
        dp[u][i]=w[u];
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        dfs(v);
        //增加一个虚构结点，所以是m+1 
        for(int j=m;j>=1;j--)
            for(int l=1;l<=j;l++)
                dp[u][j]=max(dp[u][j],dp[u][l]+dp[v][j-l]);
    }
} 

int main(){
//  freopen("data","r",stdin);
         scanf("%d%d",&n,&m);
        int a,b;
        for(int i=1;i<=n;i++){
            cin>>a>>w[i];
            G[a].push_back(i);
        }
        dfs(0);
        cout<<dp[0][m]<<endl; 

    return 0;
}