SCOI2005D2T3 | 互不侵犯

Portal

按照状压 DP 套路,第一维为行,第二维为使用的国王数,状态压缩描述第 ii 行的状态。预处理出合法状态和该状态下有几个王。当第 ii 行的状态和该状态左右移再与 i1i-1 行的状态为假才转移。直接写出状态转移方程:
Fi,j,ck+cj+=Fi1,k,ckF_{i,j,c_k+c_j}+=F_{i-1,k,c_k}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cstdio>
typedef unsigned long long ull;
int main() {
int n,num,ed,c[155];static ull s[155],f[10][155][155];
scanf("%d%d",&n,&num);ed=1<<n;f[0][1][0]=1;
for(int i=0,cnt=1;i<ed;++i,cnt=1) {
for(int j=1;j<ed;j<<=1) if(i&j)
if(i&(j<<1)) {cnt=0;break;} else ++cnt;
if(cnt) {s[++s[0]]=i;c[s[0]]=cnt-1;}
}
for(int i=1;i<=n;++i)
for(int j=1;j<=s[0];++j)
for(int k=1;k<=s[0];++k) {
if(s[j]&s[k]||s[j]&(s[k]<<1)||(s[j]<<1)&s[k]) continue;
for(int t=c[k];t+c[j]<=num;++t)
f[i][j][t+c[j]]+=f[i-1][k][t];
}
for(int i=2;i<=s[0];++i) f[n][1][num]+=f[n][i][num];
printf("%llu",f[n][1][num]);
return 0;
}

Download

本站所有原创内容采用 CC-BY-NC-ND 4.0 International 协议进行许可,附加条款亦可能应用。部分非原创内容版权为 上海アリス幻楽団黄昏フロンティア 等同人创作者所有。

题解 OI

评论

您需要成为穿墙的邪仙以加载 Disqus。