【SCOI2005】互不侵犯

发表于

题目描述

在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。 （ 1 <=N <=9, 0 <= K <= N * N）

暴力

初见此题以为是八皇后的改版八国王，拿起来直接深搜回溯，见暴力代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
long long n,k,ans,jjj;
long long bj[15][15];
void dfs(int x,int ii,int jj) {
    if(x==k+1) {
        ans++;
        return ;
    }
    for(int i=ii; i<=n; i++) {
        if(i==ii)jjj=jj;
        else jjj=1;
        for(int j=jjj; j<=n; j++) {
            if(bj[i][j]==0) {
                bj[i][j]++;bj[i-1][j]++;bj[i+1][j]++;
                bj[i+1][j+1]++;bj[i+1][j-1]++;
                bj[i-1][j+1]++;bj[i-1][j-1]++;
                bj[i][j+1]++;bj[i][j-1]++;
                dfs(x+1,i,j);
                bj[i][j]--;bj[i-1][j]--;bj[i+1][j]--;
                bj[i+1][j+1]--;bj[i+1][j-1]--;
                bj[i-1][j+1]--;bj[i-1][j-1]--;
                bj[i][j+1]--;bj[i][j-1]--;
            }
        }
    }
    return ;
}
int main() {
    cin>>n>>k;
    dfs(1,1,1);
    cout<<ans;
}

果然TLE三个点，回头一看数据大小，想来自己还是sometimes naive…

动态规划正解

既然是动态规划，就要考虑好状态和状态转移方程，虽然对于我这个蒟蒻来说找到这个状态并不容易。

我们用一个三维数组d[sta][t][kk]来表示此状态的摆放方案数，其中sta表示这一行的状态（那些点），t表示处于哪一行，kk表示剩余几个国王还没用

这样定义状态的话就不难想出状态转移方程了，我们枚举剩余的kk个国王在下一行的状态，来进行状态转移，这样我们还要对于剩余kk个国王在一行中如何排放进行预处理，用m数组维护，因此得到递归模式的方程：d[sta][t][kk]+=dfs(m[i],t+1,kk-tt)

既然是递归，我们就要考虑递归边界，显然递归边界是t==n时，若kk==0则多一种情况（返回1），否则返回0

预处理函数：

1
2
3
4
5
6
7
8
9
10
11
void pre(int x,int t,int tot2) {
    if(t>k)return;
    if(tot2==n) {
        tot++;
        m[tot]=x;
        return;
    }
    x<<=1;
    pre(x,t,tot2+1);
    if(((x>>1)&1)==0)pre(x+1,t+1,tot2+1);
}

动态规划dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
long long dfs(int sta,int t,int kk) {
    if(t==n) { //考虑边界 
        if(kk==0) return d[sta][t][kk]=1;
        else return 0;
    }
    if(d[sta][t][kk]>0)return d[sta][t][kk];
    for(int i=1; i<=tot; i++) {
        int l=m[i];
        if(((sta&l)==0)&&((sta&(l<<1))==0)&&((sta&(l>>1))==0)) {
            tt=0;
            while(l!=0) {
                if((l&1)==1)tt++;
                l>>=1;
            }
            if(kk>=tt) {
                d[sta][t][kk]+=dfs(m[i],t+1,kk-tt);
            }
        }
    }
    return d[sta][t][kk];
}

简洁明了的主函数：

1
2
3
4
5
int main() {
    cin>>n>>k;
    pre(0,0,0);//预处理 
    cout<<dfs(0,0,k);
}