题目#

中国象棋

玉米田Corn Fields

两道DP。

中国象棋#

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

换了另一种做法。

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

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

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

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

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

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

15
void init(){
16
    C[0][0] = 1;
17
    rep(i, 1, 100){
18
        rep(j, 0, i){
19
            C[i][j] = C[i-1][j] + C[i-1][j-1];
20
        }
21
    }
22
}
23
int main(int argc, char const *argv[])
24
{
25
    init();
26
    int n, m;
27
    scanf("%d %d", &n, &m);
28
    f[0][0][0] = 1;
29
    rep(i, 1, n){
30
        rep(j, 0, m){
31
            rep(k, 0, m){
32
                if(j + k > m) continue;
33
                //不选
34
                f[i][j][k] += f[i-1][j][k];
35
                f[i][j][k] %= MOD;
36

37
                //选一个 选在空列
38
                f[i][j+1][k] += f[i-1][j][k] * (m - j - k);
39
                f[i][j+1][k] %= MOD;
40
                // 选一个 选在单炮列
41
                f[i][j-1][k+1] += f[i-1][j][k] * j;
42
                f[i][j-1][k+1] %= MOD;
43

44
                // 选两个 都选在空列
45
                f[i][j+2][k] += f[i-1][j][k] * C[m - j - k][2];
46
                f[i][j+2][k] %= MOD;
47
                // 选两个 都选在单炮列
48
                f[i][j-2][k+2] += f[i-1][j][k] * C[j][2];
49
                f[i][j-2][k+2] %= MOD;
50
                // 选两个 一个在空列一个在单炮列
51
                f[i][j][k+1] += f[i-1][j][k] * (m - j - k) * j;
52
                f[i][j][k+1] %= MOD;
53
            }
54
        }
55
    }
56
    ll ans = 0;
57
    rep(i, 0, m) rep(j, 0, m) {
58
        ans += f[n][i][j];
59
        ans %= MOD;
60
    }
61
    printf("%lld\n", ans);
62
    return 0;
63
}

玉米田#

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

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

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

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

11
ll f[15][5005];
12
bool g[5005];
13
int mp[15][15];
14
int field[15];
15
int main(int argc, char const *argv[])
16
{
17
    int n, m;
18
    scanf("%d %d", &n, &m);
19
    rep(i, 1, n){
20
        rep(j, 1, m){
21
            scanf("%d", &mp[i][j]);
22
            field[i] <<= 1;
23
            field[i] |= mp[i][j];
24
        }
25
    }
26
    //求出可行状态集
27
    vector<int> sta;
28
    rep(i, 0, (1<<m)-1) if(!((i & i>>1)||(i & i<<1)))   sta.push_back(i);
29

30
    f[0][0] = 1;
31
    rep(i, 1, n) {
32
        //枚举当前行的状态
33
        for(int j: sta) {
34
            //如果和土地状况不冲突
35
            if((j & field[i]) == j) {
36
                //枚举上一行的状态
37
                for(int k: sta) {
38
                    //如果也不冲突
39
                    if((j & k) == 0) {
40
                        //可行的转移
41
                        f[i][j] += f[i-1][k], f[i][j] %= MOD;
42
                    }
43
                }
44
            }
45
        }
46
    }
47
    ll ans = 0;
48
    rep(i, 0, (1<<m)-1) {
49
        ans += f[n][i];
50
        ans %= MOD;
51
    }
52
    printf("%lld\n", ans);
53
    return 0;
54
}