P2051:[AHOI2009]中国象棋题解

这是一道比较优秀的方案数 DP 题。乍一看以为是状压 DP,然后发现数据范围过大所以只能重新思考(也就是看题解)。我们可以写出状态格式:

\[dp[ln][opit][tpit],其中 ln 为行号,opit 代表第 ln 行内一个棋子的列数,tpit 代表第 ln 行内两个棋子的列数。\]

然后我们就可以根据不同情况来进行转移了。我们来看下面几组代码,其中每组都会有对应方程的意义。我们记\(dp[ln+1]\)为当前行号。首先,我们先要判定转移源的方案数不为\(0\),之后再进行转移。

// 不放置棋子的情况;
// Situation without placing;
dp[ln + 1][opit][tpit] = (dp[ln + 1][opit][tpit] + dp[ln][opit][tpit]) % MOD;
// 在不放置棋子的位置上放置一个棋子;
// Situation of placing one on empty lines;
if (M - opit - tpit >= 1)
    dp[ln + 1][opit + 1][tpit] = (dp[ln + 1][opit + 1][tpit] + dp[ln][opit][tpit] * (M - opit - tpit)) % MOD;
// 在放置了一个棋子的位置上放置一个棋子;
// Situation of placing one on lines with only piece;
if (opit >= 1)
    dp[ln + 1][opit - 1][tpit + 1] = (dp[ln + 1][opit - 1][tpit + 1] + dp[ln][opit][tpit] * opit) % MOD;
// 在两个没有放置棋子的位置上放置两个棋子,其中 C2(num) = C^num_2;
// Situation of placing two pieces on the two empty slots;
if (M - opit - tpit >= 2)
    dp[ln + 1][opit + 2][tpit] = (dp[ln + 1][opit + 2][tpit] + dp[ln][opit][tpit] * C2(M - opit - tpit)) % MOD;
// 在一个没有棋子的位置和一个有一个棋子的位置放置共两个棋子;
// Situation of placing one on the empty and another on the only slot;
if (M - opit - tpit >= 1 && opit >= 1)
    dp[ln + 1][opit][tpit + 1] = (dp[ln + 1][opit][tpit + 1] + dp[ln][opit][tpit] * (M - opit - tpit) * opit) % MOD;
// 在两个一个棋子的位置放置共两个棋子;
// Situation of placing two on two only slots;
if (opit >= 2)
    dp[ln + 1][opit - 2][tpit + 2] = (dp[ln + 1][opit - 2][tpit + 2] + dp[ln][opit][tpit] * C2(opit)) % MOD;

完整源码:

// P2051.cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;
const int MX_N = 102, MOD = 9999973;
ll dp[MX_N][MX_N][MX_N], N, M;
ll C2(ll num)
{
    return (num * (num - 1)) / 2;
}
int main()
{
    scanf("%lld%lld", &N, &M);
    dp[0][0][0] = 1;
    for (int ln = 0; ln < N; ln++)
        for (int opit = 0; opit <= M; opit++)
            for (int tpit = 0; tpit + opit <= M; tpit++)
                if (dp[ln][opit][tpit])
                {
                    // 不放置棋子的情况;
                    // Situation without placing;
                    dp[ln + 1][opit][tpit] = (dp[ln + 1][opit][tpit] + dp[ln][opit][tpit]) % MOD;
                    // 在不放置棋子的位置上放置一个棋子;
                    // Situation of placing one on empty lines;
                    if (M - opit - tpit >= 1)
                        dp[ln + 1][opit + 1][tpit] = (dp[ln + 1][opit + 1][tpit] + dp[ln][opit][tpit] * (M - opit - tpit)) % MOD;
                    // 在放置了一个棋子的位置上放置一个棋子;
                    // Situation of placing one on lines with only piece;
                    if (opit >= 1)
                        dp[ln + 1][opit - 1][tpit + 1] = (dp[ln + 1][opit - 1][tpit + 1] + dp[ln][opit][tpit] * opit) % MOD;
                    // 在两个没有放置棋子的位置上放置两个棋子,其中 C2(num) = C^num_2;
                    // Situation of placing two pieces on the two empty slots;
                    if (M - opit - tpit >= 2)
                        dp[ln + 1][opit + 2][tpit] = (dp[ln + 1][opit + 2][tpit] + dp[ln][opit][tpit] * C2(M - opit - tpit)) % MOD;
                    // 在一个没有棋子的位置和一个有一个棋子的位置放置共两个棋子;
                    // Situation of placing one on the empty and another on the only slot;
                    if (M - opit - tpit >= 1 && opit >= 1)
                        dp[ln + 1][opit][tpit + 1] = (dp[ln + 1][opit][tpit + 1] + dp[ln][opit][tpit] * (M - opit - tpit) * opit) % MOD;
                    // 在两个一个棋子的位置放置共两个棋子;
                    // Situation of placing two on two only slots;
                    if (opit >= 2)
                        dp[ln + 1][opit - 2][tpit + 2] = (dp[ln + 1][opit - 2][tpit + 2] + dp[ln][opit][tpit] * C2(opit)) % MOD;
                }
    ll ans = 0;
    for (int i = 0; i <= M; i++)
        for (int j = 0; i + j <= M; j++)
            ans = (ans + dp[N][i][j]) % MOD;
    printf("%lld\n", ans);
    return 0;
}

 

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

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