[BZOJ1801/Luogu2051][Ahoi2009]chess 中国象棋(动态规划)

发布于 2018-02-16  18 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ1801/Luogu2051][Ahoi2009]chess 中国象棋(动态规划)

Description

在N行M列的棋盘上,放若干个炮可以是0个,使得没有任何一个炮可以攻击另一个炮。 请问有多少种放置方法,中国像棋中炮的行走方式大家应该很清楚吧.

Http

BZOJ
Luogu

Tag

动态规划

解决思路

考虑中国象棋中炮的攻击方式,发现其实就是要求任意一行或任意一列不能摆放超过两个炮。并且我们发现,每一个炮具体摆的位置不影响最后的结果,只贡献组合数。那么我们枚举行,考虑列。
设\(F[i][j][k]\)表示当前处理到第\(i\)行,前\(i\)行中,一个炮都没有的列有\(j\)个,只有一个炮的列有\(k\)个,分别转移。
首先,这一行可以什么也不摆,那就直接转移到\(F[i+1][j][k]\)。
可以选择摆一个炮,那么这个炮可以摆在原来一个炮都没有的某一列,转移到\(F[i+1][j-1]\[k+1]\),并乘上方案数\(j\);同理,这一个炮也可以摆在原来已经有一个炮的某一列上,转移到\(F[i+1][j][k-1]\),并乘上方案数\(k\)。
那么摆两个炮的也是同理,分为两个都摆在原来一个炮丢没有的列上、两个都摆在原来已经有一个的列上和一个在没有一个在已经有一个的列上,这三种情况讨论,乘上对应的系数。

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ1801/Luogu2051][Ahoi2009]chess 中国象棋(动态规划)


HNCJ OIer 一枚