GDKOI2016:染色大战【状压DP】
请输入验证码查看题目
[secret key="zj2005"]题目点击这里[/secret]
好吧其实这题跟博弈论并没有什么特别大的关系，所谓的最优策略只不过是选择在对面的分数最大的情况下选择让自己分数最高的决策。好吧很拗口，其实就是一个最大最小搜索什么的。。。然后因为数据较大所以可以使用记忆化搜索或者状压DP（好吧这两个东西经常在一起）。
考虑到总共的可以用来染色的点只有20个，所以可以把每一个点看成一个二进制位，20位的二进制数一共只有1048575个，嗯看上去很靠谱，然后思考一下DP的方程：
用f[i]代表在状态i下先手减去后手最大的分数，然后由于从一开始的状态开始推很显然会有后效性。但如果我们从最终状态往前面推，就可以去除掉前面操作对后面的影响。
那么想一想就弄出了这个东西：
f[i]=max(-f[i+j],f[i+j]+x)
其中j指的是将某个格子从黑色变成白色（对因为是倒着推）所改变的状态（也就是选择的格子所对应的二进制位），x指的是进行操作后能得到的得分。
取前面的负值就相当于染了色但是没有产生新的正方形，所以会交换先后手，那么分数就要变回原来的相反数。如果染色产生了正方形，那么会奖励一次染色机会，就不需要交换先后手，并且加上对应的分数。
至于x的算法，只要判断跟选择的位置有关的最多4个正方形的其他3个位置在染色是是不是黑色就可以，这个判断具体的实现方法很多，而且也比较简单。
代码：
var f:array[0..1048576]of longint; a,b,c:array[1..6,1..6]of longint; t:array[-1..19]of longint; n,m,i,j,k,l,p,q,x,y:longint; function max(a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; function min(a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; begin read(n,m); for i:=1 to n do for j:=1 to m do begin read(p); if p=0 then begin b[i,j]:=k; inc(k); end else b[i,j]:=-1; end; for i:=1 to n-1 do for j:=1 to m-1 do read(a[i,j]); t[0]:=1; for i:=1 to k do t[i]:=t[i-1] shl 1; q:=t[k]-1; dec(k); for i:=1 to n-1 do for j:=1 to m-1 do begin c[i,j]:=t[b[i,j]]+t[b[i,j+1]]+t[b[i+1,j]]+t[b[i+1,j+1]]; end; for i:=q-1 downto 0 do begin f[i]:=-2147483647; for j:=1 to n do for l:=1 to m do if b[j,l]<>-1 then if i and t[b[j,l]]=0 then begin p:=i+t[b[j,l]]; x:=0; if p and c[j,l]=c[j,l] then x:=x+a[j,l]; if (j>1) and (p and c[j-1,l]=c[j-1,l]) then x:=x+a[j-1,l]; if (l>1) and (p and c[j,l-1]=c[j,l-1]) then x:=x+a[j,l-1]; if (j>1) and (l>1) and (p and c[j-1,l-1]=c[j-1,l-1]) then x:=x+a[j-1,l-1]; if x=0 then f[i]:=max(f[i],-f[p]); if x<>0 then f[i]:=max(f[i],f[p]+x); end; end; writeln(f[0]); end.
发表回复