HDU 4832 Chess

思路：把行列的情況分別dp求出來，然后枚舉行用幾行。豎用幾行，然后相乘累加起來就是答案
代碼：

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;typedef long long ll;const ll MOD = 9999991;
const int N = 1005;
int t, n, m, k, x, y;
ll dp1[N][N], dp2[N][N], C[N][N];int main() {for (int i = 0; i <= 1000; i++) {C[i][0] = C[i][i] = 1;for (int j = 1; j < i; j++) {C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;}}int cas = 0;scanf("%d", &t);while (t--) {scanf("%d%d%d%d%d", &n, &m, &k, &x, &y);memset(dp1, 0, sizeof(dp1));memset(dp2, 0, sizeof(dp2));dp1[0][x] = dp2[0][y] = 1;for (int i = 1; i <= k; i++) {for (int j = 1; j <= n; j++) {if (j >= 2) dp1[i][j] = (dp1[i][j] + dp1[i - 1][j - 2]) % MOD;if (j >= 1)dp1[i][j] = (dp1[i][j] + dp1[i - 1][j - 1]) % MOD;dp1[i][j] = (dp1[i][j] + dp1[i - 1][j + 1]) % MOD;dp1[i][j] = (dp1[i][j] + dp1[i - 1][j + 2]) % MOD;}}for (int i = 1; i <= k; i++) {for (int j = 1; j <= m; j++) {if (j >= 2) dp2[i][j] = (dp2[i][j] + dp2[i - 1][j - 2]) % MOD;if (j >= 1)dp2[i][j] = (dp2[i][j] + dp2[i - 1][j - 1]) % MOD;dp2[i][j] = (dp2[i][j] + dp2[i - 1][j + 1]) % MOD;dp2[i][j] = (dp2[i][j] + dp2[i - 1][j + 2]) % MOD;}}ll heng[N], shu[N];memset(heng, 0, sizeof(heng));memset(shu, 0, sizeof(shu));for (int i = 1; i <= n; i++)for (int kk = 0; kk <= k; kk++)heng[kk] = (heng[kk] + dp1[kk][i]) % MOD;for (int i = 1; i <= m; i++)for (int kk = 0; kk <= k; kk++)shu[kk] = (shu[kk] + dp2[kk][i]) % MOD;ll ans = 0;for (int i = 0; i <= k; i++) {ans = (ans + (heng[i] * shu[k - i] % MOD) * C[k][i] % MOD) % MOD;}printf("Case #%d:\n", ++cas);cout << ans << endl;}return 0;
}

轉載于:https://www.cnblogs.com/ldxsuanfa/p/10009395.html

總結

以上是生活随笔為你收集整理的HDU 4832(DP+计数问题)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。