洛谷P2051 中国象棋（dp）

题目链接：传送门

题目大意：

　　在N行M列的棋盘中放象棋中的“炮”，问要使得“炮”两两互不伤害，有多少种放法。

　　1 ≤ n，m ≤ 100，答案对9999973取模。

思路：

　　按行更新答案。每行炮可以放在空列（下称A列）和有一个炮的列（下称B列），从而生成B列和有两个炮的列（C列），所以更新行的时候有这样几种选择：

①不放“炮”；

②选一个A列放一个“炮”，生成一个B列；

③选一个B列放一个“炮”，生成一个C列；

④选两个A列放一个“炮”，生成两个B列；

⑤选两个B列放一个“炮”，生成两个C列；

⑥选一个A列和一个B列各放一个“炮”，生成一个B列和一个C列；（注意在同一行不能放两个棋子在同一列，所以不能看作用一个A列生成一个C列）

考虑到各行各列的顺序与答案无关：

状态：

　　f[i][j][k]：第i行有j个B列和k个C列。

初始状态：

　　f[0][0][0] = 1;

状态转移方程：

　　①f[i][j][k] = f[i-1][j][k];

　　②f[i][j][k] = f[i-1][j-1][k] ×（i-1行A列个数）;

　　③f[i][j][k] = f[i-1][j+1][k-1] ×（i-1行B列个数）;

　　④f[i][j][k] = f[i-1][j-2][k] ×（i-1行A列个数选2）;

　　⑤f[i][j][k] = f[i-1][j+2][k-2] ×（i-1行B列个数选2）;

　　⑥f[i][j][k] = f[i-1][j][k-1] ×（i-1行A列个数）×（i-1行B列个数）;

注意边界和取模即可。

时间复杂度：O(nm)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAX_N = ;

const int MOD = ;

ll f[MAX_N][MAX_N][MAX_N];

inline int C(int n)

{//n选2

    return n*(n-)/;

}

int main()

{

    int N, M;

    cin >> N >> M;

    f[][][] = ;

    for (int i = ; i <= N; i++) {

        for (int j = ; j <= M; j++) {

            for (int k = ; k+j <= M; k++) {

                //放1个

                if (j- >=  && (M-(j-+k)) >= )

                    f[i][j][k] = (f[i][j][k] + f[i-][j-][k] * (M-(j-+k))) % MOD;

                if (j+ <= M && k >= )

                    f[i][j][k] = (f[i][j][k] + f[i-][j+][k-] * (j+)) % MOD;

                //放两个

                if (j- >=  && (M-(j-+k)) >= )

                    f[i][j][k] = (f[i][j][k] + f[i-][j-][k] * C(M-(j-+k))) % MOD;

                if (k >=  && (M-(j+k-)) >=  && j >= )

                    f[i][j][k] = (f[i][j][k] + f[i-][j][k-] * (M-(j+k-)) * j) % MOD;

                if (k >= )

                    f[i][j][k] = (f[i][j][k] + f[i-][j+][k-] * C(j+)) % MOD;

                //不放

                f[i][j][k] = (f[i][j][k] + f[i-][j][k]) % MOD;

            }

        }

    }

    ll ans = ;

    for (int j = ; j <= M; j++)

        for (int k = ; k+j <= M; k++)

            ans = (ans + f[N][j][k]) % MOD;

    cout << ans << endl;

    return ;

}