1. 首页
  2. Let's OI!
  3. 正文

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>

评论

0条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。