首页 > 代码库 > 树状DP入门

树状DP入门

2024-07-06 13:59:50   226人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1520

题目大意：给定一棵关系树，每个节点有个权值，子节点和父节点不能同时选，问最后能选的最大价值是多少？

解题思路：树形DP入门题。由于子节点与父节点不能同时选，有人可能会用贪心思想，二者选其一肯定最优。其实不然，有可能父节点和子节点都不选，而要选子孙节点。不过只要再往深点想下，就可以得出动态规划的解法。每个节点要么选要么不选，和大多数选不选动归一样，来个dp[i][2]，0表示不选，1表示不选，那我们只要从叶子节点往根结点不断更新dp[i][0]和dp[i][1]就可以了。

状态转移方程:dp[i[[1] = sum(dp[j][0])                      (当前选了，子节点必定不能选，最优的情况是都不选，然后累加)

                          dp[i][0] = sum(max(dp[i][0],dp[i][1]))   (当选不选，子节点可选可不选，找大的那个状态)


简单的树形DP入门题
分别用STL中的vector建了个有向图
然后又用结构体建了个无向图。
两个程序

#include<iostream>
#include<vector>
#include<cmath>
#include<cstdio>
using namespace std;
#define MAXSIZE  6050

vector<int> vec[MAXSIZE];
int weight[MAXSIZE];
int f[MAXSIZE];  //每个节点的父节点
int d[MAXSIZE][2];
int num;

//d[a][0]表示不选择该节点，d[a][1]表示选择该节点
void dfs(int a)  //用来求解d[a][0]和d[a][i]
{
    unsigned int i;
    unsigned int len=vec[a].size();
    d[a][1]=weight[a];
    for(i=0;i<len;i++)
        dfs(vec[a][i]);
    for(i=0;i<len;i++)
    {
        d[a][1]+=d[vec[a][i]][0];
        d[a][0]+=max(d[vec[a][i]][0],d[vec[a][i]][1]);
    }
}
int main()
{
    int i,a,b;
    //freopen("a.txt","r",stdin);
    while(scanf("%d",&num)!=EOF)
    {
        for(i=1;i<=num;i++)
        {
            scanf("%d",&weight[i]);
            vec[i].clear();
            d[i][0]=d[i][1]=0;
            f[i]=-1;//初始化的时候都是没有父节点的
        }
        while(scanf("%d%d",&a,&b),a+b)
        {
            f[a]=b;
            vec[b].push_back(a);
        }
        a=1;
        while(f[a]!=-1)
            a=f[a];
        dfs(a);
        cout<<max(d[a][0],d[a][1])<<endl;

    }
    return 0;
}
<pre name="code" class="cpp">//第二种方法，用结构体来构建无向图
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAXN 6050
struct node
{
    int v;
    node* next;
}*head[MAXN],tree[MAXN*2];
bool vis[MAXN];
int weight[MAXN];
int ptr,num;
int d[MAXN][2];

void init()
{
    ptr=1;
    memset(vis,false,sizeof(vis));
    memset(head,NULL,sizeof(head));
}

void addEdge(int a,int b)         //该段是模块化编程
{                                 //所有的关于树形DP问题采用无向图方式表示地
    tree[ptr].v=b;                //都是这样构造无向图的
    tree[ptr].next=head[a];       //采用2个一维的数组表示的
    head[a]=&tree[ptr++];
    tree[ptr].v=a;
    tree[ptr].next=head[b];
    head[b]=&tree[ptr++];
}
void bfs(int root)
{
    if(vis[root])   //记忆化搜索，vis[root]为true表示已经求过d[root]
        return ;
    vis[root]=true;
    d[root][1]=weight[root];
    node* p=head[root];
    while(p)
    {
        if(!vis[p->v])  //只有没访问过才求其值
        {
            bfs(p->v);
            d[root][1]+=d[p->v][0];
            d[root][0]+=max(d[p->v][0],d[p->v][1]);
        }
        p=p->next;
    }
}
int main()
{
    int i,a,b;
    freopen("a.txt","r",stdin);
    while(scanf("%d",&num)!=EOF)
    {
        init();
        for(i=1;i<=num;i++)
            scanf("%d",&weight[i]);
        while(scanf("%d%d",&a,&b),a+b)
            addEdge(a,b);
        bfs(1);
        printf("%d\n",max(d[1][0],d[1][1]));
    }



}



































        

            
                
                  
                
                

                    联系

                    我们