P2465 [SDOI2008] 山贼集团

模拟赛的 T0。

题解

观察

P

的范围，发现可以状压，往这方面考虑。发现对于一个节点

u

，管控其的分部即为

u

子树内的分部。

设

dp_{u,S}

表示节点

u

，其子树内的分部集合为

S

的最大收益。那么有初始化就是

dp_{u,S} = \sum_{x \in S} a_{u,x}

，也就是直接在

u

修建

S

内的所有分部。

合并子节点和父亲节点的过程形如树上背包，也就是

dp_{u,S \cup T} = \max(dp_{v,T},dp_{u,S})

。

直接做转移就可以了。注意还要加上分部合作带来的价值，记

g_{S}

为一个节点的子树内有分部

S

带来的贡献，

g_{S}

的计算也比较简单，为

g_{S} = \sum_{T \subset S} val_{T}

。

枚举子集时间复杂度为

3^P

，总时间复杂度为

O(N 3^P)

。

code:

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define il inline
#define lb(x) ((x)&(-(x)))
const int N=102,maxp=13;
const ll lnf=-(1e15+38);
int n,m,rep,sta;
ll a[1<<maxp],dp[N][1<<maxp];
ll dvt[1<<maxp];
namespace Graph{
	int hd[N],cnt=0;
	struct edge{int to,nxt;}e[N<<1];
	void ade(int from,int to){e[++cnt]={to,hd[from]};hd[from]=cnt;}
}using namespace Graph;
il void gmx(ll &x,ll y){x=max(x,y);}
void dfs(int u,int fa){
	for(int i=hd[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==fa) continue;
		dfs(v,u);
		for(int s=sta;s;s--) for(int t=s;t;t=(t-1)&s) gmx(dp[u][s],dp[u][s^t]+dp[v][t]);//树上背包
	}
	for(int s=1;s<=sta;s++) dp[u][s]+=dvt[s];//加上分部合作的贡献
	
}
int main(){
	cin>>n>>rep;sta=(1<<rep)-1;
	for(int i=1,u,v;i<n;i++){
		cin>>u>>v;
		ade(u,v);ade(v,u);
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<rep;j++) cin>>a[1<<j];
		for(int s=1;s<=sta;s++) for(int t=s;t;t^=lb(t)) dp[i][s]-=a[lb(t)];//初始化dp数组
	}
	cin>>m;
	for(int val,num,x,s;m;m--){
		cin>>val>>num;s=0;
		for(;num;num--){
			cin>>x;
			s|=(1<<(x-1));
		}
		dvt[s]+=val;//即上文中的g数组
	}
	for(int s=sta;s;s--) for(int t=s&(s-1);t;t=(t-1)&s) dvt[s]+=dvt[t];//注意s要从大到小枚举，因为正着更新会导致某些值被重复计算，可以利用树上背包的思想
	dfs(1,0);
	cout<<dp[1][sta]<<'\n';
	return 0;
}

题解：P2465 [SDOI2008] 山贼集团

文章操作

P2465 [SDOI2008] 山贼集团

题解

相关推荐

评论

题解：P2465 [SDOI2008] 山贼集团