bzoj1801[Ahoi2009]chess 中国象棋【多维DP】
题目点击这里
这个,题目的数据是100×100的,所以暴力DFS肯定是不行的啦~
由于每行每列最多只能放2个炮,所以可以用一个三维DP
用f[i,j,k]表示放完第i行的炮后,现在有j列有1个炮,k列有2个炮,当然,1个炮都没有的列数就是m-j-k。然后递推一下就可以。
(懒得手打就直接上图吧)
嗯,就差不多这样了。
代码:
const modd:longint=9999973; var f:array[0..100,0..100,0..100]of int64; n,m,i,j,k,ans:longint; begin read(n,m); f[0,0,0]:=1; for i:=1 to n do for j:=0 to m do for k:=0 to m-j do begin f[i,j,k]:=f[i-1,j,k]; if j>0 then f[i,j,k]:=(f[i,j,k]+f[i-1,j-1,k]*(m-j-k+1)) mod modd; if (j<m ) and (k>0) then f[i,j,k]:=(f[i,j,k]+f[i-1,j+1,k-1]*(j+1)) mod modd; if j>1 then f[i,j,k]:=(f[i,j,k]+f[i-1,j-2,k]*(m-j-k+2)*(m-j-k+1) div 2) mod modd; if (j</m><m -1) and (k>1) then f[i,j,k]:=(f[i,j,k]+f[i-1,j+2,k-2]*(j+2)*(j+1) div 2) mod modd; if (j>0) and (k>0) then f[i,j,k]:=(f[i,j,k]+f[i-1,j,k-1]*(m-k-j+1)*(j)) mod modd; end; ans:=0; for i:=0 to m do for j:=0 to m-i do begin ans:=(ans+f[n,i,j]) mod modd; end; writeln(ans); end.</m>
发表回复