BZOJ 1801 [AHOI2009]chess 中国象棋:dp

题目

题目描述

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

输入格式

一行包含两个整数N,M,之间由一个空格隔开。

输出格式

总共的方案数,由于该值可能很大,只需给出方案数模9999973的结果。

说明/提示

样例说明

除了3个格子里都塞满了炮以外,其它方案都是可行的,所以一共有222-1=7种方案。

数据范围

100%的数据中N和M均不超过100

50%的数据中N和M至少有一个数不超过8

30%的数据中N和M均不超过6

题解

计数?应该可以dp吧

首先很显然的是,如果要让炮互相打不到,那么一行或一列中,最多放两个炮

下面开始dp

怎么表示状态?可不可以一个一个放:“当前放到了位置 (i,j),这一行左边已经放了 k 个,这一列上面放了 t 个”?好像不太行,因为这样的话好像并没有办法转移。

考虑一行一行放:f[i][j][k][t] 表示已经放完了前 i 行,目前有 j 列还没有放,有 k 列放了一个,有 t 列放了两个。很显然的是,由于 j+k+t=m,所以第四维可以省略,即:f[i][j][k]

怎么转移?在当前这一行中,最多只能放两个炮,而且只能放在空列(方便起见,记作c0)或放了一个的列(记作c1)上。

所以放的方案如下:

  • 放两个,放到两个c0上,下个状态为:f[i+1][j-2][k+2]
  • 放两个,放到两个c1上,下个状态为:f[i+1][j][k-2]
  • 放两个,分别放到一个c0和一个c1上,下个状态:f[i+1][j-1][k]
  • 放一个,放到c0上,下个状态:f[i+1][j-1][k+1]
  • 放一个,放到c1上,下个状态:f[i+1][j][k-1]
  • 不放,下个状态:f[i+1][j][k]

如果确定了一种放的方案,具体怎么放还有许多种不同的方法。

所以转移(顺推)的时候,就是 f[下个状态] += f[i][j][k] * 对于当前方案放的方法数,即:

f[i + 1][j - 2][k + 2] += f[i][j][k] * ((j * (j - 1)) >> 1)
f[i + 1][j][k - 2] += f[i][j][k] * ((k * (k - 1)) >> 1)
f[i + 1][j - 1][k] += f[i][j][k] * (j * k)
f[i + 1][j - 1][k + 1] += f[i][j][k] * j
f[i + 1][j][k - 1] += f[i][j][k] * k
f[i + 1][j][k] += f[i][j][k]

统计答案?我们要的是所有放完第n行的方案数之和:
ans = \sum_{j=0}^m\sum_{k=0}^m f[n][j][k]

最后,初始值:
f[0][m][0] = 1
表示还没有放的时候,m列全是空列,没有放了一个的列,共有一种方案

还有就是,运算过程中弄不好会int溢出,暴力加个long long就好了。

Code

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 105
#define MOD 9999973
#define int long long

using namespace std;

int n, m, ans = 0;
int f[MAX_N][MAX_N][MAX_N];

signed main() {
    scanf("%lld%lld", &n, &m);
    f[0][m][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= m; j++) {
            for (int k = 0; k <= m; k++) {
                if (j - 2 >= 0) {
                    f[i + 1][j - 2][k + 2] = (f[i + 1][j - 2][k + 2] + f[i][j][k] * ((j * (j - 1)) >> 1)) % MOD;
                }
                if (k - 2 >= 0) {
                    f[i + 1][j][k - 2] = (f[i + 1][j][k - 2] + f[i][j][k] * ((k * (k - 1)) >> 1)) % MOD;
                }
                if (j - 1 >= 0) {
                    f[i + 1][j - 1][k] = (f[i + 1][j - 1][k] + f[i][j][k] * (j * k)) % MOD;
                    f[i + 1][j - 1][k + 1] = (f[i + 1][j - 1][k + 1] + f[i][j][k] * j) % MOD;
                }
                if (k - 1 >= 0) {
                    f[i + 1][j][k - 1] = (f[i + 1][j][k - 1] + f[i][j][k] * k) % MOD;
                }
                f[i + 1][j][k] = (f[i + 1][j][k] + f[i][j][k]) % MOD;
            }
        }
    }
    for (int j = 0; j <= m; j++) {
        for (int k = 0; k <= m; k++) {
            ans = (ans + f[n][j][k]) % MOD;
        }
    }
    printf("%lld\n", ans);
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注