题解 P2465 【[SDOI2008]山贼集团】

· · 题解

这里介绍一种又快又短的可爱代码。

首先，我们预处理一个数组 g_i，表示 i 集合中的分部如果同时可以管某个点，这个点带来的贡献。这个可以通过一个高维前缀和在 O(p2^p) 时间内简单求出。

然后，我们开始DP。设 f[x,i] 表示节点 x 如果被 i 中集合管，此时的最大收益。初始值就是 i 集合中的分部开在 x 的费用。这个可以通过简单地 O(2^p) 地一遍DP即可预处理出来。

然后开始树上背包。明显这里应该使用 O(3^p) 的子集枚举拼凑出原数组；为了节省时空消耗，采取倒序DP的方式，就不用另开辅助数组了。

最后统计额外消耗。枚举 i，令 f[x,i] 增加 g_i 即可。此部分 O(2^p) 解决。

总复杂度 O(p2^p+n2^p+n3^p+n2^p)=O(n3^p)。

代码（883B）：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,q,lim;
ll f[110][1<<12],g[1<<12];
vector<int>v[110];
void dfs(int x,int fa){
    for(int i=0;i<lim;i++)f[x][i]=f[x][i^(i&-i)]+f[x][i&-i];
    for(auto y:v[x]){
        if(y==fa)continue;
        dfs(y,x);
        for(int i=lim-1;i;i--)for(int j=i;j;j=(j-1)&i)f[x][i]=max(f[x][i],f[x][i^j]+f[y][j]);
    }
    for(int i=0;i<lim;i++)f[x][i]+=g[i];
}
int main(){
    scanf("%d%d",&n,&m),lim=1<<m;
    for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
    for(int i=1;i<=n;i++)for(int j=0,x;j<m;j++)scanf("%d",&x),f[i][1<<j]=-x;
    scanf("%d",&q);
    for(int i=1,x,y,z,w;i<=q;i++){
        scanf("%d%d",&x,&y),w=0;
        while(y--)scanf("%d",&z),w|=(1<<(z-1));
        g[w]+=x;
    }
    for(int i=0;i<m;i++)for(int j=0;j<lim;j++)if(j&(1<<i))g[j]+=g[j^(1<<i)];
    dfs(1,0);
    printf("%lld\n",f[1][lim-1]);
    return 0;
}