树形DP

初涉树形DP

题目链接

https://cn.vjudge.net/problem/POJ-2342#author=TCGOGOGO

题目大意

一棵树有n个结点,每个结点有一个权值,一个结点和其直接的父亲结点不能同时选,求按照要求所能选到的点权和的最大值

解题思路

从下向上转移即可,dp[i][0]代表第i个节点不参加的最有解,dp[i][1]代表第i个节点参加的最优解。
转移方程:
dp[i][0]+=max(dp[j][0],dp[j][1])
dp[i][1]+=dp[j][0]
j为后继节点,签到题没啥好说的,但是体现出了树形DP的基本形态。

代码

#include <iostream>
#include <cstring>
const int maxn=6060;
using namespace std;
struct node{
    int v,next;
}edge[maxn*2];
int head[maxn];
int dp[maxn][2];
int ru[maxn];
int cnt;
void add(int u,int v){
    edge[cnt]={v,head[u]};
    head[u]=cnt++;
}
void dfs(int rt){
    for(int i=head[rt];i!=-1;i=edge[i].next){
        int v=edge[i].v;
        dfs(v);
        dp[rt][1]+=dp[v][0];
        dp[rt][0]+=max(dp[v][0],dp[v][1]);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    int n;
    while(cin>>n&&n){
        cnt=0;
        memset(head,-1,sizeof(head));
        memset(dp,0,sizeof(dp));
        memset(ru,0,sizeof(ru));
        for(int i=1;i<=n;i++){
            cin>>dp[i][1];
        }
        int u,v;
        for(int i=1;i<n;i++){
            cin>>u>>v;
            add(v,u);
            ru[u]++;
        }
        int rt;
        for(int i=1;i<=n;i++){
            if(ru[i]==0){
                rt=i;
            }
        }
        dfs(rt);
        cout<<max(dp[rt][0],dp[rt][1])<<endl;
    }
    return 0;
}

树形DP提高

题目一:

And And And 西安邀请赛 J 题(点分治应用/树形DP)

发表评论

电子邮件地址不会被公开。 必填项已用*标注