「SCOI2011」地板 - 插头DP | Bill Yang's Blog

「SCOI2011」地板 - 插头DP

题目大意

    lxhgww的小名叫“小L”,这是因为他总是很喜欢L型的东西。小L家的客厅是一个$R\times C$的矩形,现在他想用L型的地板来铺满整个客厅,客厅里有些位置有柱子,不能铺地板。现在小L想知道,用L型的地板铺满整个客厅有多少种不同的方案?
    需要注意的是,如下图所示,L型地板的两端长度可以任意变化,但不能长度为0。铺设完成后,客厅里面所有没有柱子的地方都必须铺上地板,但同一个地方不能被铺多次。


题目分析

越来越糊涂了,插头DP都调了两个小时。
换了一种Hash的方法,应该速度有提升。
用$0$表示无插头,$1$表示一个可以转弯可以伸长的插头,$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
#include<bits/stdc++.h>
using namespace std;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
const int mod=20110520,hashmod=99599;
int n,m,bit[15],f[2][200005],a[105][105],status[2][200005],cnt[2],now,pre;
char mp[105][105];
vector<int> edges[hashmod];
void add(int &x,int v) {x+=v;if(x>=mod)x-=mod;}
void trans(int s,int sum) {
int pos=s%hashmod;
for(int i:edges[pos])if(status[now][i]==s) {add(f[now][i],sum);return;}
status[now][++cnt[now]]=s;
f[now][cnt[now]]=sum;
edges[pos].push_back(cnt[now]);
}
int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++)scanf("%s",mp[i]+1);
for(int i=1; i<=11; i++)bit[i]=(i-1)<<1;
if(n<m) {
char tmp[105][105];
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
tmp[j][i]=mp[i][j];
memcpy(mp,tmp,sizeof(tmp));
swap(n,m);
}
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)a[i][j]=mp[i][j]=='*'?0:1;
f[0][1]=cnt[0]=1;
now=0,pre=1;
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
swap(now,pre);
cnt[now]=0;
for(int k=0; k<hashmod; k++)edges[k].clear();
for(int k=1; k<=cnt[pre]; k++) {
int S=status[pre][k],p=(S>>bit[j])&3,q=(S>>bit[j+1])&3,val=f[pre][k];
if(!a[i][j]) {if(!p&&!q)trans(S,val);continue;}
if(!p&&!q) {
if(a[i+1][j])trans(S^1<<bit[j],val);
if(a[i][j+1])trans(S^1<<bit[j+1],val);
if(a[i+1][j]&&a[i][j+1])trans(S^(1<<bit[j])<<1^(1<<bit[j+1])<<1,val);
} else if(!q) {
if(p==1) {
if(a[i+1][j])trans(S^1<<bit[j]^(1<<bit[j])<<1,val);
if(a[i][j+1])trans(S^1<<bit[j]^1<<bit[j+1],val);
} else {
trans(S^(1<<bit[j])<<1,val);
if(a[i][j+1])trans(S^(1<<bit[j])<<1^(1<<bit[j+1])<<1,val);
}
} else if(!p) {
if(q==1) {
if(a[i+1][j])trans(S^1<<bit[j]^1<<bit[j+1],val);
if(a[i][j+1])trans(S^1<<bit[j+1]^(1<<bit[j+1])<<1,val);
} else {
trans(S^(1<<bit[j+1])<<1,val);
if(a[i+1][j])trans(S^(1<<bit[j])<<1^(1<<bit[j+1])<<1,val);
}
} else if(p+q==2)trans(S^1<<bit[j]^1<<bit[j+1],val);
}
}
for(int j=1; j<=cnt[now]; j++)status[now][j]<<=2;
}
printf("%d\n",cnt[now]?f[now][1]:0);
return 0;
}
本篇文章有用吗?有用还不快点击!
0%