luogu1896互不侵犯题解--状压DP

题目链接

https://www.luogu.org/problemnew/show/P1896

分析

做过玉米田的应该不难设计出状态转移与预处理

$f[sta][i][j]$表示第$i$行状态为$sta$,总共已经放了$j$个的方案数

$f[sta][i][j] = \sum f[p][i-1][j-num[sta]]$

$num[sta]$是$sta$二进制表示下$1$的个数,当然要保证$p,sta$都是合法的并且$p$与$sta$能够相邻

所以我们要预处理处每个状态本身是否合法,若状态$x$合法,我们再预处理出状态$x$中二进制下每个$1$左右都变成$1$的状态称其为$sta[x]$，实际上这两个是能同时预处理出来的

显然若$i$行状态为$x$,我们使用刷表法的话,第$i-1$的状态$y$必须满足$y$&$sta[x]==0$并且$num[x]<k,num[x]+num[y]<k$的前提

棋子最多$n^2$个，数组别开小了

代码

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <queue>
#include <iostream>
#define ll long long 
#define ri register int 
using std::min;
using std::max;
template <class T>inline void read(T &x){
    x=0;int ne=0;char c;
    while(!isdigit(c=getchar()))ne=c=='-';
    x=c-48;
    while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
    x=ne?-x:x;return ;
}
const int maxn=19260817;
const int inf=0x7fffffff;
ll f[1<<10][11][85];//state - row - cnt
//放了几个棋子的数组别开小了
int n,k,sz;
bool ok[1<<10];
int sta[1<<10],num[1<<10];
int main(){
    int x,y,p,cnt=0;
    bool flag;
    read(n),read(k);
    if(n==1){
        if(k==1)puts("1");
        else if(k==0)puts("1");
        else puts("orz");
        return 0;
    }
    memset(f,0,sizeof(f));
    sz=1<<n;
    for(ri i=0;i<sz;i++){//预处理
        p=i,cnt=0;
        for(ri j=0;j<n;j++){
            if(i&(1<<j)){
                cnt++;
                if(j==0){//第一列和第N列的需单独考虑
                    if(i&(1<<(j+1))){
                        ok[i]=1;
                        break;
                    }
                    p=p|(1<<(j+1));
                }
                else if(j==n-1){
                    if(i&(1<<(j-1))){
                        ok[i]=1;
                        break;
                    }
                    p=p|(1<<(j-1));      
                }
                else{
                    if(i&(1<<(j+1))){
                        ok[i]=1;
                        break;
                    }
                    if(i&(1<<(j-1))){
                        ok[i]=1;
                        break;
                    }
                    p=p|(1<<(j+1));
                    p=p|(1<<(j-1));
                }
            }
        }
        if(ok[i])continue;
        sta[i]=p;//1向左右扩展后的状态
        num[i]=cnt;//二进制下一的个数
    }
    f[0][0][0]=1;
    for(ri r=1;r<=n;r++){
        for(ri i=0;i<sz;i++){
            if(ok[i])continue;
            if(num[i]>k)continue;
            x=sta[i];
            for(ri j=0;j<sz;j++){
                if(ok[j])continue;
                if(x&j)continue;
                if(num[i]+num[j]>k)continue;              
                for(ri o=num[j]+num[i];o<=k;o++){
                    f[i][r][o]+=f[j][r-1][o-num[i]];
                }
            }
        }
    }
    ll ans=0;
    for(ri i=0;i<sz;i++)ans+=f[i][n][k];
    printf("%lld\n",ans);
    return 0;
}