【洛谷P2051】中国象棋【dp】

本文主要是介绍【洛谷P2051】中国象棋【dp】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

题目链接：https://www.luogu.org/problem/P2051
这次小可可想解决的难题和中国象棋有关，在一个N行M列的棋盘上，让你放若干个炮（可以是0个），使得没有一个炮可以攻击到另一个炮，请问有多少种放置方法。大家肯定很清楚，在中国象棋中炮的行走方式是：一个炮攻击到另一个炮，当且仅当它们在同一行或同一列中，且它们之间恰好有一个棋子。你也来和小可可一起锻炼一下思维吧！

思路：

显然每一行每一列最多只能有两个棋子。
所以设 $f [i] [j] [k]$ 表示前 $i$ 行，有 $j$ 列放了一个棋子，有 $k$ 列放了两个棋子的方案数。
那么对于第 $i$ 行，有以下五种转移方式：

不放置棋子
放一个棋子在没有棋子的列
放一个棋子在原本已经有一个棋子的列
放两个棋子在原本都没有棋子的列
放两个棋子分别在没有棋子的列和有一个棋子的列
放两个棋子分别在两个已有一个棋子的列

注意每次转移都要乘上一个组合数。
时间复杂度 $O(nm^2)$

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;const int N=110,MOD=9999973;
ll ans,f[N][N][N];
int n,m; ll C(int x,int y)
{return x*(x-1)/2;
}int main()
{scanf("%d%d",&n,&m);f[0][0][0]=1;for (int i=1;i<=n;i++)for (int j=0;j<=m;j++)for (int k=0;j+k<=m;k++){f[i][j][k]=f[i-1][j][k];if (j>=1) f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k]*(m-j-k+1))%MOD;if (k>=1) f[i][j][k]=(f[i][j][k]+f[i-1][j+1][k-1]*(j+1))%MOD;if (j>=2) f[i][j][k]=(f[i][j][k]+f[i-1][j-2][k]*C(m-j-k+2,2))%MOD;if (k>=1) f[i][j][k]=(f[i][j][k]+f[i-1][j][k-1]*j*(m-j-k+1))%MOD;if (k>=2) f[i][j][k]=(f[i][j][k]+f[i-1][j+2][k-2]*C(j+2,2))%MOD;}for (int i=0;i<=m;i++)for (int j=0;i+j<=m;j++)ans=(ans+f[n][i][j])%MOD;printf("%lld",ans);return 0;
}