洛谷P1879 & P2051

题目

中国象棋

玉米田Corn Fields

两道DP。

中国象棋

以为是状压DP，但是不知道怎么做。

换了另一种做法。

显然，每列不可能有两个以上的炮，设 $f[i][j][k]$ 表示第 $i$ 行有 $j$ 列有一个炮车，有 $k$ 列有两个炮车。那么一个炮车也没有个列数就是 $m-j-k$。

定义完状态，再来想怎么转移。考虑从 $i-1$ 行向 $i$ 行转移。第 $i$ 行最多只能有两个炮车分情况讨论：

1. 不放炮车，$f[i][j][k] = f[i-1][j][k]$
2. 放一个炮车，放在没有跑车的列或者有一个炮车列：$f[i][j+1][k] = f[j-1][j][k] * (m-j-k), f[i][j][k+1] = f[i-1][j][k]*j$
3. 放两个炮车的情况，讨论一下就好了，看代码吧。

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define per(i, a, b) for(int i = (a); i >= (b); --i)
#define debug(x) cerr << #x << ' ' << x << endl;
using namespace std;

typedef long long ll;
const int MOD = 9999973;
const int MAXN = 2e5 + 7;

//第i行有j个单跑k个双炮
ll f[105][105][105];
ll C[105][105];

void init(){
    C[0][0] = 1;
    rep(i, 1, 100){
        rep(j, 0, i){
            C[i][j] = C[i-1][j] + C[i-1][j-1];
        }
    }
}
int main(int argc, char const *argv[])
{
    init();
    int n, m;
    scanf("%d %d", &n, &m);
    f[0][0][0] = 1;
    rep(i, 1, n){
        rep(j, 0, m){
            rep(k, 0, m){
                if(j + k > m) continue;
                //不选
                f[i][j][k] += f[i-1][j][k];
                f[i][j][k] %= MOD;
                
                //选一个 选在空列
                f[i][j+1][k] += f[i-1][j][k] * (m - j - k);
                f[i][j+1][k] %= MOD;
                // 选一个 选在单炮列
                f[i][j-1][k+1] += f[i-1][j][k] * j;
                f[i][j-1][k+1] %= MOD;
                
                // 选两个 都选在空列
                f[i][j+2][k] += f[i-1][j][k] * C[m - j - k][2];
                f[i][j+2][k] %= MOD;
                // 选两个 都选在单炮列
                f[i][j-2][k+2] += f[i-1][j][k] * C[j][2];
                f[i][j-2][k+2] %= MOD;
                // 选两个 一个在空列一个在单炮列
                f[i][j][k+1] += f[i-1][j][k] * (m - j - k) * j;
                f[i][j][k+1] %= MOD;
            }
        }
    }
    ll ans = 0;
    rep(i, 0, m) rep(j, 0, m) {
        ans += f[n][i][j];
        ans %= MOD;
    }
    printf("%lld\n", ans);
    return 0;
}

玉米田

状压DP，先保存每一行的状态，在求出有效的状态。

枚举有效的状态，判断是否和土地状况冲突，不冲突再枚举上一行的状态，如果和当前行不冲突，那么就是有效的转移。

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define per(i, a, b) for(int i = (a); i >= (b); --i)
#define debug(x) cerr << #x << ' ' << x << endl;
using namespace std;

typedef long long ll;
const int MOD = 1e9;
const int MAXN = 2e5 + 7;

ll f[15][5005];
bool g[5005];
int mp[15][15];
int field[15];
int main(int argc, char const *argv[])
{
    int n, m;
    scanf("%d %d", &n, &m);
    rep(i, 1, n){
        rep(j, 1, m){
            scanf("%d", &mp[i][j]);
            field[i] <<= 1;
            field[i] |= mp[i][j];
        }
    }
    //求出可行状态集
    vector<int> sta;
    rep(i, 0, (1<<m)-1) if(!((i & i>>1)||(i & i<<1)))   sta.push_back(i);
    
    f[0][0] = 1;
    rep(i, 1, n) {
        //枚举当前行的状态
        for(int j: sta) {
            //如果和土地状况不冲突
            if((j & field[i]) == j) {
                //枚举上一行的状态
                for(int k: sta) {
                    //如果也不冲突
                    if((j & k) == 0) {
                        //可行的转移
                        f[i][j] += f[i-1][k], f[i][j] %= MOD;
                    }
                }
            }
        }
    }
    ll ans = 0;
    rep(i, 0, (1<<m)-1) {
        ans += f[n][i];
        ans %= MOD;
    }
    printf("%lld\n", ans);
    return 0;
}