题解：P12444 [COTS 2025] 发好奖 / Hijerarhija

首先，~~为了资本做局~~，员工

i

的奖金一定只有三种取值：

0,1,c_i

。

然后可以直接当树形背包问题做，但你发现

dp

数组的合并复杂度炸了。所以这个问题肯定不能直接当树形背包做。考虑换个思路。

注意本题的唯一特殊条件：如果

i

有正整数奖金，那么

fa_i

也有正整数奖金，也就是

i

的所有祖先都得有奖金。

可以联想到（但是有点难联想到）dfs 序，因为对于节点

v

以及它的任意一个祖先

u

，都满足

u

在 dfs 序上的位置严格小于

v

；同时，一颗子树内的节点，在 dfs 序上也是连续的。

那么我们在 dfs 序上做这个背包问题，设

dp_{i,j}

表示 dfs 序前

i

个员工总共拿

j

元奖金，

\sum p

的最大值。转移也自然分为三种：

dp_{i+siz_{dfn_i},j}=\max(dp_{i+siz_{dfn_i},j},dp_{i,j})

dp_{i+1,j+1}=\max(dp_{i+1,j+1},dp_{i,j})

dp_{i+1,j+c_{dfn_i}}=\max(dp_{i+1,j+c_{dfn_i}},dp_{i,j}+p_{dfn_i})

注意这里的第一个转移，从

i

直接转移到

i+siz_{dfn_i}

是为了不给

dfn_i

子树内员工发放奖金。

时间复杂度

\Theta(nk)

。

CPP

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
#define pii pair<int,int>
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define ro(i,r,l) for(int i=r;i>=l;i--)
const int N=5005;
int n,m,a[N],b[N];
vector<int>e[N];
int dfn[N],tip,siz[N];
int dp[N][N];
void dfs(int u){
    dfn[++tip]=u;
    siz[u]=1;
    for (auto v:e[u]){
        dfs(v);
        siz[u]+=siz[v];
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    fo(i,2,n){
        int fa;
        cin>>fa;
        e[fa].push_back(i);
    }
    dfs(1);
    fo(i,1,n)
        cin>>a[i];
    fo(i,1,n)
        cin>>b[i];
    memset(dp,-0x3f,sizeof dp);
    dp[1][0]=0;
    fo(i,1,n){
        int x=dfn[i];
        fo(j,0,m){
            dp[i+siz[x]][j]=max(dp[i+siz[x]][j],dp[i][j]);
            if (j<m)
                dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]);
            if (j+b[x]<=m)
                dp[i+1][j+b[x]]=max(dp[i+1][j+b[x]],dp[i][j]+a[x]);
        }
    }
    int rs=0;
    fo(i,0,m)
        rs=max(rs,dp[n+1][i]);
    cout<<rs<<'\n';
    return 0;
}

题解：P12444 [COTS 2025] 发好奖 / Hijerarhija

文章操作

相关推荐

评论

题解：P12444 [COTS 2025] 发好奖 / Hijerarhija