题解 P1352 【没有上司的舞会】

Rocket_raccoon_ · 2019-02-20 13:58:33 · 题解

上司和职员的关系构成一棵树。由于是求最优解，并且每一个节点的取舍关乎全局，因此，此题可用树型动态规划。
任何一点的取舍可以看做一种决策，状态就是在某个点取或者不取。我们可用f[i][0]存储不选i节点的最优解，f[i][1]存储选V的节点的最优解，具体来说：
1.当取i点时，他的所有儿子都不取，即f[i][1]=sum(f[i.son][0]）+i;
2.不取i点时，可取他的儿子或不取，即f[i][0]=sum(max(f[i.son][0],f[i.son][1]));
则ans=max（f[root][0],f[root][1])

代码如下

#include<iostream>
#include<cstdio>
using namespace std;
int n,f[6010][2],p[6010],ans,t,l,r;
bool vis[6001];

void dp(int x){
    int i;
    if (!vis[x]){
        vis[x]=1;
        for (i=1; i<=n; i++){
            if (p[i]==x){
                if (!vis[i]) dp(i);
                f[x][1]+=f[i][0];
                f[x][0]+=max(f[i][0],f[i][1]);
            }
        }
    }
}

int main(){
    int i;

    cin>>n;

    t=1;
    while (t<=n){//输入每个人的价值
        cin>>f[t++][1];
    }
    cin>>l>>r;
    while (l!=0&&r!=0){
        p[l]=r;
        cin>>l>>r;
    }
    for (i=1; i<=n; i++){
        dp(i);//树型动规
    }
    for (i=1; i<=n; i++){//选最优解
        ans=max(ans,max(f[i][0],f[i][1]));
    }

    cout<<ans;

    return 0;
}