题目链接：戳这里
题目大意：
\(①\) 给你一个 \(n*m\) 的棋盘
\(②\) 问你有多少种放炮的方案使得炮不会相互攻击
\(③\) 炮的规则和中国象棋一样
前置知识：
\(①\) 首先你需要知道炮的规则是什么 (不会请自行百度)
\(②\) 你还需要掌握一些组合数学的东西
比如说基本的排列组合公式和加法乘法原理
\(③\) 你还要有一颗能看出这是一个DP的大脑
开始正文：
首先要找到本题的状态：
本题只有一个限制条件：那就是每一个 行 和 列 最多放 两个 炮
那就可以考虑状态要把一个 行 或 列 放了 多少个 炮 考虑进去
那么状态很简单就能出来了:
\(f[i][j][k]\) 表示当前在第 \(i\) 行，有 \(j\) 列放了一个炮，有 \(k\) 列放了两个炮的方案数
(很简单得就把炮的限制考虑了进去)
下面考虑转移：
\(①\) 首先这一列可以不放，那么直接由上一列转移过来
\(f[i][j][k] = f[i – 1][j][k]\)
\(②\) 也可以放一个
放在有一个棋子的列上:
\(f[i][j][k] += f[i – 1][j + 1][k – 1] * (j + 1 )\)
放在没有棋子的列上：
\(f[i][j][k] += f[i – 1][j – 1][k] * (m – (j – 1)- k)\)
解释：
放在一个棋子的列:
我们在某一个有一个棋子列放置棋子,会使这一列变为有两个棋子
即我们要得到 \(f[i][j][k]\) 需要在 \(j + 1\) 个有一个棋子的列放置棋子,变为 \(j\) 个有一个棋子的列
而我们又会得到一个新的有两个棋子的列.因此我们之前必须有 \(k – 1\) 个有两个棋子的列
而我们又可以在 \(j + 1\) 中的任何一列放置这一个棋子
因此我们要 \(* (j + 1)\)
放在没有棋子的列:
在一个没有棋子的列放置棋子,我们会得到一个新的有一个棋子的列
即我们要从 \(j – 1\) 得到 \(j\)
又因为我在空列中的任何一列放置这个棋子.
所以要 \(*(m – (j – 1) – k)\)
\(③\) 也可以放两个
一个放在一个炮的列，一个放在没有炮的列：
\(f[i][j][k] += f[i – 1][j][k – 1] * j * (m – (j – 1) – k)\)
两个都放在没有放过炮的地方：
\(f[i][j][k] += f[i – 1][j – 2][k] * C(m – (j – 2) – k)\)
两个都放在有一个炮的地方：
\(f[i][j][k] += f[i – 1][j + 2][k – 2] * C(j + 2)\)
注：以上的 \(C(x)\) 指的是 C(2, x)， 一下同理;
绝对不是我不会打
解释：
如果一个放在一个跑的列，一个放在没放炮的列:
那么放两个炮的列的数量就会加一，放一个炮的数量也会增加一
放在一个炮的地方有 \(j\) 种可能, 放在没有炮的地方有 \(m – (j – 1) – k\) 种可能
所以需要 $ j(m – (j – 1) – k)
如果放在没有放过炮的地方:
放一个炮的列就会加二
同时又有 \(C(m – (j – 2) – k)\) 种可能
所以需要 \(*(m – (j – 2) – 2)\)
如果两个都放在有一个炮的地方：
那么就有 \(C(j + 2)\) 种可能
所以要 \(*C(j + 2)\)
把每种情况都讲的这么详细了，不考虑点个赞吗
在学不会可以剖腹了
愉悦的代码时间：
(一定要注意边界条件)（千万别直接抄）
/*
／＞ フ
| _ _|
／`ミ _x 彡
/ |
/ ヽ ?
／￣| | | |
| (￣ヽ＿_ヽ_)_)
＼二つ
*/
#include<bits/stdc++.h>
using namespace std;
const int mod = 9999973;
long long read()
{
long long x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
long long f[110][110][110], n, m, ans;
long long c(long long x)//计算组合数
{
return (x * (x - 1) / 2) % mod;
}
int main()
{
n = read(), m = read();
f[0][0][0] = 1;
for(int i = 1; i <= n; i++)
{
for(int j = 0; j <= m; j++)
{
for(int k = 0; k <= m - j; k++)
{
f[i][j][k] = f[i - 1][j][k];
if(k >= 1) f[i][j][k] += (f[i - 1][j + 1][k - 1] * (j + 1));//放在有一个棋子的列
if(j >= 1) f[i][j][k] += (f[i - 1][j - 1][k] * (m - j - k + 1));//放在没有棋子的列
if(k >= 2) f[i][j][k] += f[i - 1][j + 2][k - 2] * c(j + 2);//都有一个棋子的列
if(k >= 1) f[i][j][k] += f[i - 1][j][k - 1] * j * (m - j - k + 1);//一个有棋子，一个没有棋子
if(j >= 2) f[i][j][k] += f[i - 1][j - 2][k] * c(m - j - k + 2);//都没有棋子的列
f[i][j][k] %= mod;//不要忘记取模
}
}
}
for(int i = 0; i <= m; i++)
{
for(int j = 0; j <= m; j++)
{
ans += f[n][i][j];//统计每种情况下的方案次数
ans %= mod;//不要忘记取模
}
}
cout << ans;
return 0;
}
总结：
这道题还是挺考验思维的，建议反复思考每种情况的公式及其推导，加深理解，最好搭配上自己的理
解，自己再推一遍，收获真的很不一样（千万别只看题解，自己也要手推一遍）
原文地址：http://www.cnblogs.com/Han-han-/p/16818041.html
