[NOI2006]网络收费

Posted on | In

一道难度较大的树形$DP$思维题

考虑设$dp[i][j]$为以$i$节点为根，有$j$个$B$类叶子节点的子树的最小费用

对于每一对叶子节点$i$和$j$，它们的贡献$f_{i,j}$只会在它们的$Lca_{i,j}$上计算

那么可以把$f_{i,j}$先记录在它们的$Lca_{i,j}$上

然后考虑$dfs$维护$dp$，预处理出每个叶子节点可能产生的贡献

最后根据$A$和$B$两类叶子节点个数的限制，分情况进行转移即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int m,n,ans,tmp,t[1088],vis[12],c[1088][2],f[1088][12],dp[2102][1088];
inline int read () {
	char ch=getchar(); int num=0;
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) num=(num<<3)+(num<<1)+(ch^'0'),ch=getchar();
	return num;
}
inline int lca (int x,int y) {
	for(register int i=n-1;i>=0;--i)
	    if((x>>i)^(y>>i)) return n-i-1;
}
inline void dfs (int x,int dep,int l,int r) {
	if(dep==n) {
		dp[x][0]=c[x-m][0],dp[x][1]=c[x-m][1];
		for(register int i=n-1;i>=0;--i) dp[x][vis[i]^1]+=f[x-m][i];
		return ;
	}
	memset(dp[x],INF,sizeof(dp[x]));
	register int mid=(l+r)>>1;
	vis[dep]=0; dfs(x<<1,dep+1,l,mid),dfs(x<<1|1,dep+1,mid+1,r);
	for(register int i=0;i<=mid-l+1;++i)
	    for(register int j=0;j<=r-mid&&i+j<=r-l+1;++j)
	        if(i+j<=r-l-i-j+1) dp[x][i+j]=min(dp[x][i+j],dp[x<<1][i]+dp[x<<1|1][j]);
	vis[dep]=1; dfs(x<<1,dep+1,l,mid),dfs(x<<1|1,dep+1,mid+1,r);
	for(register int i=0;i<=mid-l+1;++i)
	    for(register int j=0;j<=r-mid&&i+j<=r-l+1;++j)
	        if(i+j>r-l-i-j+1) dp[x][i+j]=min(dp[x][i+j],dp[x<<1][i]+dp[x<<1|1][j]);
}
int main () {
	n=read(),m=1<<n; ans=INF;
	for(register int i=0;i<m;++i) t[i]=read();
	for(register int i=0;i<m;++i) c[i][t[i]^1]=read();
	for(register int i=0;i<m-1;++i)
	    for(register int j=i+1;j<m;++j)
	        tmp=read(),f[i][lca(i,j)]+=tmp,f[j][lca(i,j)]+=tmp;
	dfs(1,0,1,m);
	for(register int i=0;i<=m;++i) ans=min(ans,dp[1][i]);
	printf("%d\n",ans);
	return 0;
}