PDF版

Description:

有个公司要举行一场晚会。
为了能玩得开心,公司领导决定:如果邀请了某个人,那么一定不会邀请他的上司
(上司的上司,上司的上司的上司……都可以邀请)。
每个参加晚会的人都能为晚会增添一些气氛,求一个邀请方案,使气氛值的和最大。

Input:

第1行一个整数N(1<=N<=6000)表示公司的人数。
接下来N行每行一个整数。第i行的数表示第i个人的气氛值x(-128<=x<=127)。
接下来每行两个整数L,K。表示第K个人是第L个人的上司。
输入以0 0结束。

Output:

一个数,最大的气氛值和。

Sample Input:

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0

Sample Output:

5

解题思路:

这道题以前是做过的啊…现在来做竟然不会做了…

刚开始是想从父亲转移到儿子…后面发现题目贡献是每一层的贡献都要加起来…然后就挂了…

后面才发现应该是从儿子转移到父亲(这个算正难则反嘛…),突然发现很简单转移了…

我们设f[i][0/1]表示i这个点取或不取的最大气氛和。转移方程如下:

f[x][0]+=max(f[son][0],f[son][1])

f[x][1]+=f[v][0]

f[x][0]初值为0f[x][1]初值为a[x]

然后先递归下去将儿子的答案都处理好,在回溯的时候处理x的值。

/*Program from Luvwgyx*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=6e3+10;
struct node{int to,nxt;}e[maxn<<1];
int n,tot,ans,a[maxn],head[maxn],fa[maxn],f[maxn][2];
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
void write(int x){print(x);puts("");}
void add(int u,int v){e[++tot].to=v;e[tot].nxt=head[u];head[u]=tot;}
void dfs(int x){
    f[x][0]=0;f[x][1]=a[x];
    for(int i=head[x],v=e[i].to;i;i=e[i].nxt,v=e[i].to)dfs(v);
    for(int i=head[x],v=e[i].to;i;i=e[i].nxt,v=e[i].to){
        f[x][0]+=max(f[v][0],f[v][1]);
        f[x][1]+=f[v][0];
    }
}
int main(){
    n=read();for(int i=1;i<=n;i++)a[i]=read();
    while(1){
        int x=read(),y=read();
        if(!x&&!y)break;
        add(y,x);fa[x]=y;
    }int i;
    for(i=1;i<=n;i++)if(!fa[i]){dfs(i);break;}
    write(max(f[i][0],f[i][1]));
    return 0;
}

发表评论