題目鏈接
首先想到狀壓dp，但是\(n,m\)高達(dá)100，怎么壓？
容易發(fā)現(xiàn)，每行每列最多兩個(gè)象棋，否則就直接gg了。
一個(gè)巧妙的設(shè)置狀態(tài)的方式是，只需要記錄到當(dāng)前行有多少列是放了1個(gè)炮和2個(gè)炮。
然后每一行有3種選擇：不放、放1個(gè)、放2個(gè)。分情況轉(zhuǎn)移就行了。

#include <cstdio> const int MOD = 9999973; const int MAXN = 110; int n, m, ans; long long f[MAXN][MAXN][MAXN]; int C(int x){ //C(x,2)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]) %= MOD; //不放(f[i][j + 1][k] += f[i - 1][j][k] * (m - j - k)) %= MOD; //在沒(méi)有棋子的列放1個(gè)if(j) (f[i][j - 1][k + 1] += f[i - 1][j][k] * j) %= MOD; //在有棋子的列放1個(gè)(f[i][j + 2][k] += f[i - 1][j][k] * C(m - j - k)) %= MOD; //在沒(méi)有棋子的列放2個(gè)(f[i][j][k + 1] += f[i - 1][j][k] * (m - j - k) * j) %= MOD; //一個(gè)放在有棋子的列，一個(gè)放啊沒(méi)有棋子的列if(j > 1) (f[i][j - 2][k + 2] += f[i - 1][j][k] * C(j)) %= MOD; //放2個(gè)在有棋子的列}for(int i = 0; i <= m; ++i)for(int j = 0; i + j <= m; ++j)(ans += f[n][i][j]) %= MOD;printf("%d\n", ans);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Qihoo360/p/10918258.html

總結(jié)

以上是生活随笔為你收集整理的【洛谷 P2051】 [AHOI2009]中国象棋（DP）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。