斯德哥尔摩 的博客

斯德哥尔摩 的博客

P1352 没有上司的舞会

posted on 2018-10-24 19:37:31 | under 刷题 |

P1352 没有上司的舞会

头一次写树形$DP$的板子题,竟然$1A$!

好开森啊!!!

首先,我们知道这是棵树(废话。。。)。

然后对于每个选择有后效性,我们自然想到只考虑上司对下属的限制。

然后开始$DP$。

设$dp[i][0/1]$表示对于第$i$个节点的子树,选与不选$i$的能获得的最大价值。

由于有负值,于是状态转移方程长这个样:$$dp[i][0]+=\max\left\{\begin{array}{}0\\dp[j][0]\\dp[j][1]\end{array}\right.$$

$$dp[i][1]+=\max\left\{\begin{array}{}0\\dp[j][0]\end{array}\right.$$

其中$j$为$i$的儿子。

然后一遍$DFS$即可。

附代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 6010
using namespace std;
int n,root,ans,c=1;
int val[MAXN],head[MAXN],deep[MAXN],fa[MAXN],dp[MAXN][2];
struct Edge{
    int next,to;
}a[MAXN<<1];
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
    return date*w;
}
inline void add_edge(int x,int y){
    a[c].to=y;a[c].next=head[x];head[x]=c++;
    a[c].to=x;a[c].next=head[y];head[y]=c++;
}
void dfs(int rt){
    dp[rt][0]=0;
    dp[rt][1]=val[rt];
    for(int i=head[rt];i;i=a[i].next){
        int will=a[i].to;
        if(deep[will])continue;
        deep[will]=deep[rt]+1;
        dfs(will);
        dp[rt][0]+=max(0,max(dp[will][0],dp[will][1]));
        dp[rt][1]+=max(0,dp[will][0]);
    }
}
void work(){
    ans=max(dp[root][0],dp[root][1]);
    printf("%d\n",ans);
}
void init(){
    int x,y;
    n=read();
    for(int i=1;i<=n;i++)val[i]=read();
    for(int i=1;i<n;i++){
        x=read();y=read();
        fa[x]=y;
        add_edge(x,y);
    }
    for(int i=1;i<=n;i++)if(!fa[i]){root=i;break;}
    deep[root]=1;
    dfs(root);
}
int main(){
    init();
    work();
    return 0;
}