洛谷P2051 中国象棋状压dp

jujimeizuo

2020-08-12

ACM

P2051 [AHOI2009]中国象棋状压dp

思路

因为在同一行或同一列中最多放两个炮，所以可以放0、1、2个炮，三个以上的就不合法，因为可以互相打。

对于状态压缩dp，首先需要假设状态，这题的状态就是0、1、2，（列是指第i行中1~m列）0代表一列中没有炮，1代表一列中有一个炮，2代表一列中有2个炮，从第一行往下遍历，寻找所有的状态。

所以我们定义一个数组dp[i][j][k]，第一维表示前i行，第二维表示有j列只有一个炮，第三维表示只有k列有两个炮

那么根据容斥原理可知，没有炮的列数有m-j-k列。

因为一列中最多放两个棋子，且对于每一行，每一列只能放一个，不能说放两个，难道让他们结合吗？这里笔者就想当然的结合了，然后就错了。所以我们可以讨论以下三种情况（所有情况的第i行都是由第i-1行继承下来）：

不放棋子第i行的状态可以由第i-1行状态继承，即$dp[i][j][k]=dp[i - 1][j][k]$。
- 放一个棋子该棋子放在有一个棋子的列上在j列中拿出一列+1个棋子成为k列中的一员，即$dp[i][j][k]=dp[i-1][j][k+1]*(j+1)$ 该棋子放在空列上在空列中拿出一列成为j列的一员，即$dp[i][j][k]=dp[i-1][j-1][k]*(m-j-k+1)$
放两个棋子两个棋子分别放在两个空列上在空列中拿出两列成为j列的两员，即$dp[i][j][k]=dp[i-1][j-2][k]*C_{m-j-k+2}^2$
两个棋子一个在有棋子的列一个在空列中在j列中拿出一个成为k列的一员，在空列中拿出一个成为j列的一员，即 $dp[i][j][k]=dp[i-1][j][k-1]*j*(m-j-k+1)$
两个棋子分别放在两个有棋子的列上在j列拿出两个成为k列的两员，即 $dp[i][j][k]=dp[i-1][j+2][k-2]*C_{j+2}^2$
两个棋子放在没有棋子的一列上这是错误的，上面说道，对于每一行，只能在一列中放一个，不能放两个，否则就会“结合”了。

Code

##include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pdd;

##define INF 0x7f7f7f
##define mem(a, b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)

// const ll mod = 998244353;
// const int maxn = 1e5 + 10;
// const double eps = 1e-6;

const int mod =  9999973;

ll dp[105][105][105];

int n, m;

void solve() {
    cin >> n >> m;
    dp[0][0][0] = 1;
    for(int i = 1;i <= n; i++) {
        for(int j = 0;j <= m; j++) {
            for(int k = 0;k <= m - j; k++) {
                dp[i][j][k] = dp[i - 1][j][k]; // 不放棋子
                if(k >= 1) dp[i][j][k] += dp[i - 1][j + 1][k - 1] * (j + 1); // 放一个棋子在有一个棋子的列
                if(j >= 1) dp[i][j][k] += dp[i - 1][j - 1][k] * (m - j + 1 - k); // 放一个棋子在没有棋子的列
                if(j >= 2) dp[i][j][k] += dp[i - 1][j - 2][k] * ((m - j - k + 2) * (m - j - k + 1) / 2); // 放两个棋子在没有棋子的两列
                if(k >= 1) dp[i][j][k] += dp[i - 1][j][k - 1] * j * (m - j - k + 1); // 放两个在一列有棋子一列无棋子
                if(k >= 2) dp[i][j][k] += dp[i - 1][j + 2][k - 2] * ((j + 2) * (j + 1) / 2); // 放两个在两列都有棋子
                dp[i][j][k] %= mod;
            }
        }
    }
    ll ans = 0;
    for(int j = 0;j <= m; j++) {
        for(int k = 0;k <= m - j; k++) {
            ans = (ans + dp[n][j][k]) % mod;
        }
    }
    cout << ans << endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    //cin.tie(nullptr);
    //cout.tie(nullptr);
##ifdef FZT_ACM_LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    signed test_index_for_debug = 1;
    char acm_local_for_debug = 0;
    do {
        if (acm_local_for_debug == '$') exit(0);
        if (test_index_for_debug > 20)
            throw runtime_error("Check the stdin!!!");
        auto start_clock_for_debug = clock();
        solve();
        auto end_clock_for_debug = clock();
        cout << "Test " << test_index_for_debug << " successful" << endl;
        cerr << "Test " << test_index_for_debug++ << " Run Time: "
             << double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl;
        cout << "--------------------------------------------------" << endl;
    } while (cin >> acm_local_for_debug && cin.putback(acm_local_for_debug));
##else
    solve();
##endif
    return 0;
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2020/08/12/luogu-p2051/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！

P2051 [AHOI2009]中国象棋 状压dp

思路

Code

P2051 [AHOI2009]中国象棋状压dp