NOI2006 网络收费
题目大意：
“配对收费”的方式
合理的改变每一个叶子节点的颜色（付费方式）
使改变档案费用+配对收费总和最小
40%的数据中N≤4
80%的数据中N≤7
100%的数据中N≤10
节点个数=2^n。
要点一：看懂系数表 做的时候就卡在这里了，囧！！
配对收费的规则
B较多时， AA 收费系数为2
AB 收费系数为1
BB 收费系数为0
其他情况反之
设想：
B较多时，在每一个A结点上有1个收费系数
否则在每一个B结点上有1个收费系数
要点二：由于决策对之前的费用有影响，先规定一些决策(fatherS)，
状态：opt[i,cntA,fatherS]
表示下述子问题的最优解
以i结点为根的子树
管辖的叶子中，A的数目为cntA（可算B的数目）
祖先的状态存储在fatherS中
即每一个祖先管辖叶子中，A还是B多
状态转移:opt[i,cntA,fatherS]
枚举i的左孩子中A的数目cntA1
在所有可行解中opt[left(i), cntA1, fatherS + nowS] +opt[right(i), cntA – cntA1, fatherS + nowS]取最小值
边界条件: i是叶子
根据cntA计算改变颜色需要的费用，
根据cntA和fatherS计算加在这个叶子节点上的配对费用
初看时间复杂度：80分, M = 2N
状态O(M3)
时间复杂度为O(M4)
要点三：
仔细分析状态opt[i,cntA,fatherS]
假设A有k个祖先
则cntA有2N-k种可能,fatherS有2k种可能
状态有O(M2)个
而转移平摊复杂度为O(log2M)=O(N)
证明：总的转移次数为∑K=0 to N 2^(N-K){枚举的cntA1的数目}*2^K {这一层的节点数}*M{cntA和fatherS连起来的状态 数}=N*M^2
所以时间复杂度为O(M2N): 100分
存储状态：对于每一层的节点滚动实现，把2^(N-K)与2^K接起来同放在一维状态中，充分利用状态。
这个实现应该是比较漂亮的了。
program xqz; const maxn=1024; oo=1 shl 30; var f:array[0..1,0..maxn,0..maxn*2] of longint; w:array[0..maxn,0..maxn] of longint; c,a:array[0..maxn] of longint; i,j,k,m,n,l,r,dep,ans,s,t:longint; function max(a,b:longint):longint; begin if a>b then max:=a else max:=b; end; function min(a,b:longint):longint; begin if a<b then min:=a else min:=b; end; begin assign(input,'network.in'); reset(input); assign(output,'network.out'); rewrite(output); read(n); inc(n); m:=1 shl (n-1); for i:=1 to m do read(a[i]); for i:=1 to m do read(c[i]); for i:=1 to m do begin for j:=i+1 to m do begin read(w[i,j]); w[j,i]:=w[i,j]; end; for j:=1 to m do w[i,j]:=w[i,j-1]+w[i,j]; end; t:=0; s:=1; for i:=1 to m do for j:=0 to m*2 do begin if not((a[i]=1)xor odd(j)) then f[t,i,j]:=c[i]; l:=i; r:=j shr 1; for k:=0 to n-2 do begin if odd(j) xor odd(r) then if odd(l) then inc(f[t,i,j],w[i,(l+1)*(1 shl k)]-w[i,l*(1 shl k)]) else inc(f[t,i,j],w[i,(l-1)*(1 shl k)]-w[i,(l-2)*(1 shl k)]); l:=(l+1) shr 1; r:=r shr 1; end; end; for dep:=n-1 downto 1 do begin s:=(s+1) and 1; t:=(t+1) and 1; for i:=1 to 1 shl (dep-1) do for j:=0 to m*2 do begin if (dep=2)and(i=1)and(j=5) then k:=k; f[t,i,j]:=oo; l:=j and(1 shl (n-dep+1)-1); if l>1 shl (n-dep) then continue; r:=((j shr (n-dep+1)) shl 1+ord(l>=1 shl (n-dep-1))) shl (n-dep); for k:=max(l-1 shl (n-dep-1),0) to min(l,1 shl (n-dep-1)) do f[t,i,j]:=min(f[t,i,j],f[s,i shl 1-1,r+k]+f[s,i shl 1,r+l-k]); end; end; ans:=oo; for i:=0 to m do ans:=min(ans,f[t,1,i]); writeln(ans); close(input); close(output); end.
