BZOJ 1495 网络收费

发表于 | 更新于

Link

没有表示出状态，因为叶节点的不会记录，而叶节点的状态对后来的转移也是产生影响的。 之前也做过涉及到未来费用的题目，但是远远没有这个毒瘤。

Solution

可以看出两种情况是对称的。找一下它们的共同点：同0/2 不同 1 进而可以发现一个点对对答案产生的贡献是可以分开统计的： 当nA<nBnA < nB时，每个AA都会对答案产生一倍的贡献； 当nB≥nBnB \ge nB时，每个BB都会对答案产生一倍贡献。 这个转换是明显等价的，这样就把计算过程大大简化了，由计算点对变成了计算点。 那么，对于一个点uu，如果它任意一个祖先点pp的nAnA和nBnB的大小关系确定了，那么uu对pp的贡献也就确定了。 而祖先的这种大小关系可以用一个二进制串SS表示。由此，设计状态如下 f[i][nA][S]f[i][nA][S]表示在以ii为根的子树中有nAnA个AA节点，ii的所有祖先状态为SS的时候，子树子树中的点对答案产生的最小贡献。 转移基本就和普通的树形DP相同了。 但是这样会MLE：nAnA的上界是2n2^n，SS的上界是111...111,n−1111...111,n-1个11，所以也是O(2n)O(2^n)级别。 然而，可以发现nAnA和SS是互相制约的，深度越浅的点，子树中的节点越多，但是到祖先的路径越短、状态总数越少。于是，可以把nAnA和SS这两维压到一起存储。 所以这个题就呵呵了

Code

如果有谁A掉了这个题，万望解答我在注释中的疑问 

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int INF=0x7f7f7f7f,MAXN=11,A=0,B=1;
int lca(int x,int y)
{
	while(x!=y) (x>y?x:y)>>=1;
	return x;
}
int sum(int x,int y){return x==INF||y==INF?INF:x+y;}
int dep[1<<MAXN],init[1<<MAXN],pay[1<<MAXN],flow[1<<MAXN][1<<MAXN],n,sumc[1<<MAXN][MAXN],f[1<<MAXN][1<<MAXN<<1];
void DP(int pos)//定义路由器的颜色为数量少的颜色
{
	int id=pos-(1<<n)+1,divider=n-dep[pos]+1,covers=(1<<divider>>1);
	if(dep[pos]==n)
	{
		for(int S=0;S<=(1<<dep[pos])-1;++S)//总量为1是A 0是B
		{
			f[pos][(init[id]^1)+(S<<divider)]=pay[id];
			f[pos][init[id]+(S<<divider)]=0;
			for(int i=dep[pos]-1;~i;i--)
				if(((S>>i)&1)==A) f[pos][1+(S<<divider)]+=sumc[id][i];
				else f[pos][0+(S<<divider)]+=sumc[id][i];
		}
	}
	else
	{
		int ls,rs,sonD=divider-1;DP(ls=pos<<1),DP(rs=pos<<1|1);
		for(int fl=0;fl<=(covers>>1);fl++)
			for(int fr=0;fr<=(covers>>1);fr++)
			{
				for(int S=0;S<=(1<<dep[pos])-1;++S)
				{
					int kind;
					//f[i][j][k]表示在以i节点为根的子树，有j个A，祖先状态为K的最小代价
					//把第二第三维压成(j+(k<<UPLIM)
					if((fl+fr)<=(covers-fl-fr)) kind=A; 						
					else kind=B;
					//这里判断当前节点的类型
					//如果改成<会WA
					
					int sonS=S|(kind<<dep[pos]);
					//int sonS=S|(((fl+fr)>(covers-fl-fr))<<dep[pos]);
					chkmn(f[pos][fl+fr+(S<<divider)],sum(f[ls][fl+(sonS<<sonD)],f[rs][fr+(sonS<<sonD)]));
				}
			}
	}
}
int main()
{
	get(n);
	
	dep[0]=-1;
	for(int i=1;i<=(1<<n<<1)-1;i++) dep[i]=dep[i>>1]+1;

	for(int i=1;i<=(1<<n);i++) get(init[i]);
	for(int i=1;i<=(1<<n);i++) get(pay[i]);
	for(int i=1;i<=(1<<n)-1;i++)
		for(int j=i+1;j<=(1<<n);j++)
			get(flow[i][j]);
	for(int i=1;i<=(1<<n)-1;i++)
		for(int j=i+1;j<=(1<<n);j++)
		{
			int d=dep[lca(i+(1<<n)-1,j+(1<<n)-1)];
			sumc[i][d]+=flow[i][j],sumc[j][d]+=flow[i][j];
		}
	memset(f,0x7f,sizeof(f));//sizeof(127) heheda
	DP(1);
	int Ans=INF;
	for(int i=0;i<=(1<<n);i++)
		chkmn(Ans,f[1][i]);
	printf("%d\n",Ans);
	return 0;
}
/* AC Record(Bugs) *
 * 
 * * * * * * * * * */