• P1352 没有上司的舞会


    --------------------

    链接:Miku

    --------------------

    很入门的树形dp,首先,在这个题中,我们要做的就是求出来每一个子节点,然后用他们去更新父亲节点。

    对于每一个节点,他有两种状态,去,或者不去,我们定义dp[i][0]为第i个节点也去的状态,而dp[i][1]为它不去,那么很显然

    如果这个点去了,它的子节点肯定不去,那么dp[i][1]=dp[孩子们][0]的和,

    如果这个点不去,它的子节点可以去也可以不去,那么就是dp[i][0]=max(dp[孩子们][0],dp[sons][1])的和

    ----------------------

     1 #include<iostream>
     2 #include<map>
     3 #include<cstdio>
     4 using namespace std;
     5 int n;
     6 int r[6001];
     7 int ru[6001];
     8 int x,y;
     9 int p;
    10 int dp[6001][2];
    11 int head[6001];
    12 struct b{
    13     int t;
    14     int ne;
    15 } e[6001];
    16 void add(int f,int to){
    17     p++;
    18     e[p].t=to;
    19     e[p].ne=head[f];
    20     head[f]=p;
    21 }
    22 int ro;
    23 void dfs(int now){
    24     dp[now][0]=0;
    25     dp[now][1]=r[now];
    26     for(int i=head[now];i;i=e[i].ne){
    27         dfs(e[i].t);
    28         dp[now][0]+=max(dp[e[i].t][1],dp[e[i].t][0]);
    29         dp[now][1]+=dp[e[i].t][0];
    30     }
    31 }
    32 int main(){
    33     cin>>n;
    34     for(int i=1;i<=n;++i){
    35         scanf("%d",&r[i]);
    36     }
    37     for(int i=1;i<=n-1;++i){
    38         scanf("%d%d",&x,&y);
    39         add(y,x);
    40         ru[x]++;
    41     }
    42     for(int i=1;i<=n;++i){
    43 //        cout<<ru[i]<<" ";
    44         if(!ru[i]){
    45             ro=i;
    46             break;
    47         }
    48     }
    49 //    cout<<ro<<endl;
    50     dfs(ro);
    51     cout<<max(dp[ro][0],dp[ro][1]);
    52     return 0;
    53 }
    Ac
  • 相关阅读:
    自动脚本工具新版 v2.0
    Flash 导出图片和声音
    as3 工具类分享 CookieMgr
    时间戳与时间
    OpenGL 加载位图(BMP)贴图
    as3+java+mysql(mybatis) 数据自动工具(七)
    as3+java+mysql(mybatis) 数据自动工具(六)
    as3+java+mysql(mybatis) 数据自动工具(五)
    as3+java+mysql(mybatis) 数据自动工具(四)
    将博客搬至CSDN
  • 原文地址:https://www.cnblogs.com/For-Miku/p/12219501.html
一二三 - 开发者的网上家园