首页 > 其他 > 详细

hdu 1054

时间:2019-03-16 00:47:50      阅读:24      评论:0      收藏:0      [点我收藏+]

标签:祖先   mes   sum   ref   print   hdu   节点   details   names   

这是一道树形dp的题 最近有点想学dp但各种高深操作还是学不来

题目大意是给你一颗树,在树的节点上放置士兵,需要用最少的士兵来沾满所有的边.

由于每个节点只有放士兵和不放士兵两个状态且子节点的来源与当前节点没有关系,(儿子的儿子放不放并不影响父亲)就满足了dp的条件

#include<bits/stdc++.h> 

#define ll  long long 
using namespace std;

const int MAXN = 1510;
int vis[MAXN];
struct node
{
    int bro,child;
    int fa;
}Node[MAXN];
int dp[MAXN][2];
void DFS(int x)//dfs更新
{
    int child = Node[x].child;
    while(child)
    {
        DFS(child);//优先更新孩子
        dp[x][1] +=min(dp[child][1],dp[child][0]);  //利用孩子更新当前dp值
        dp[x][0] += dp[child][1];
        child = Node[child].bro;    //遍历所有孩子
    }
}

int main()
{
    
    int n;
    int root,k,v;
    while(cin >> n)
    {
        
        memset(vis,0,sizeof(vis));
        int Root;   //树根
        for(int i=0;i<n;++i)
        {
            scanf("%d:(%d)",&root,&k);
            root++;
            if(i==0)    Root = root;
            if(!vis[root])  //对于新加入的节点 以该节点建立新树
            {
                vis[root] = true;
                Node[root].bro = Node[root].fa = Node[root].child = 0;
                dp[root][1] =1;
                dp[root][0] = 0;
            }
            while(k--)
            {
                scanf("%d",&v);
                v++;
                if(!vis[v]) //该节点肯定是当前树的叶子
                {
                    vis[v] = true;
                    dp[v][1] = 1;
                    dp[v][0] = 0;
                }
                Node[v].bro=Node[root].child;//更新祖先和兄弟
                Node[v].fa = root;
                Node[root].child = v;
                Node[v].child = 0;
            }
        }
        DFS(Root);
        printf("%d\n",min(dp[Root][1],dp[Root][0]));
    }
    return 0;
}

状态方程:

\[dp[i][0] = \sum_{j\in i.child}dp[j][1] \]
\[dp[i][1] = \sum_{j\in i.child} min(dp[j][1],dp[j][0])\]
当前节点不选 则所以孩子都得选,
当前节点选了 则孩子节点选不选都行.

叶子节点:

dp[i][0] = 0 dp[1][1] = 1

思路来源

hdu 1054

标签:祖先   mes   sum   ref   print   hdu   节点   details   names   

原文:https://www.cnblogs.com/xxrlz/p/10540282.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号