题解 P2051 【[AHOI2009]中国象棋】

· · 题解

好像不是很难

首先要想出来，每行最多只能放两个棋子，这是显然的

于是决策就是一行一行地处理

30分的做法就是裸的枚举，暴搜，枚举这一行放哪里，放几个

然后我想到了压位dp，按3进制表示当前棋盘的状态，即某一列没有棋子，或者有一个，两个棋子，能过50分

接着可以发现，棋子的顺序是无所谓的，并不需要准确知道当前棋盘的状态

于是有了100分做法：dp[i][j][k]表示放了前i行，有j列是有1个棋子，有k列有两个棋子

转移显然，分类讨论，乘法和加法原理，代码注释中写的很详细

我居然20min淦了省选题？蛤蛤蛤

蛤蛤蛤居然还是1A

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 101;
const int MOD = 9999973;
int n,m;
ll dp[MAXN][MAXN][MAXN];
inline int C( int num ) { // 相当于C(num,2)
    return num*(num-1)/2;
}
int main() {
    scanf( "%d%d", &n, &m );
    dp[0][0][0] = 1;
    for( int i = 0; i < n; ++i ) // 放第i+1行
    for( int j = 0; j <= m; ++j ) // 有1个棋子的列数
    for( int k = 0; j+k <= m; ++k ) if( dp[i][j][k] ) { // 有2个棋子的列数
        dp[i+1][j][k] = ( dp[i+1][j][k] + dp[i][j][k] ) % MOD; // 不放
        if( m-j-k >= 1 ) dp[i+1][j+1][k] = ( dp[i+1][j+1][k] + dp[i][j][k]*(m-j-k) ) % MOD; // 放一个，在没有棋子的那一列
        if( j >= 1 ) dp[i+1][j-1][k+1] = ( dp[i+1][j-1][k+1] + dp[i][j][k]*j ) % MOD; // 放一个，在有一个棋子的那一列
        if( m-j-k >= 2 ) dp[i+1][j+2][k] = ( dp[i+1][j+2][k] + dp[i][j][k]*C(m-j-k) ) % MOD; // 放两个，都在没有棋子的两列
        if( m-j-k >= 1 && j >= 1 ) dp[i+1][j][k+1] = ( dp[i+1][j][k+1] + dp[i][j][k]*(m-j-k)*j ) % MOD; // 放两个，一个在没有棋子的列，一个在有一个棋子的列
        if( j >= 2 ) dp[i+1][j-2][k+2] = ( dp[i+1][j-2][k+2] + dp[i][j][k]*C(j) ) % MOD; // 两个，在一个棋子的列
    }
    ll ans = 0;
    for( int i = 0; i <= m; ++i ) // 有1个棋子的列
    for( int j = 0; i+j <= m; ++j ) { // 2个棋子的列
        ans = ( ans + dp[n][i][j] ) % MOD;
    }
    printf( "%lld\n", ans );
    return 0;
}