「CQOI2015」标识设计 - 状态压缩+插头DP | Bill Yang's Blog
0%

「CQOI2015」标识设计 - 状态压缩+插头DP

题目大意

    一家缩写为 LLL 的公司正在设计 logo,他们的初步方案是在一张方格上放置三个 L 形的图案以及一些额外的装饰性图形。例如:

    (灰色区域表示装饰性图形)

    三个 L 图案和装饰性图形均放置在方格之中,且必须占满方格,「L」的横竖笔画长短均可,但长度必须大于零(即不能退化为一条线段)。另外,为了使 L 图形醒目且容易识别,设计师规定三个 L 形图案之间不能有重叠或交叉的部分。当然,L 形图案也不能穿过装饰图形或与之重叠。

    现在设计师已经确定了所有装饰性图形的位置,希望你计算一下放置不同的 L 形图案总共可以设计出多少个 logo。


题目分析

简单插头DP。
设$f(i,j,a,b,c,x,k)$表示转移到$(i,j)$位置,第一个下插头在轮廓线上$j=a$的位置,$\cdots\cdots$,$(i,j)$处轮廓线上是否有右插头($x$),当前已经用了$k$个插头。

转移分为几类,下插头可以向下延续,也可以断掉一个下插头让它右转,还可以新开一个插头往下走($k\lt3$)。
右插头可以向右延续,也可以直接断掉。


代码

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
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

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 maxn=35,maxs=5005;

struct pii {
int a,b,c;
pii(int a=0,int b=0,int c=0):a(a),b(b),c(c) {}
} state[maxs];

int n,m,cnt=0,id[maxn][maxn][maxn];
LL f[2][maxs][2][4];
char mp[maxn][maxn];

void Clear(LL f[][2][4],int id) {for(int s=1; s<=cnt; s++)for(int k=0; k<4; k++)f[s][id][k]=0;}

int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++)scanf("%s",mp[i]+1);
for(int i=0; i<=m; i++)
for(int j=i?i+1:0; j<=m; j++)
for(int k=j?j+1:0; k<=m; k++) {
state[++cnt]=pii(i,j,k);
id[i][j][k]=id[i][k][j]=id[j][i][k]=id[j][k][i]=id[k][i][j]=id[k][j][i]=cnt;
}
f[0][1][0][0]=1;
int now=0,pre=1;
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
swap(now,pre);
Clear(f[now],0),Clear(f[now],1);
for(int s=1; s<=cnt; s++)
for(int k=0; k<4; k++) {
int a=state[s].a,b=state[s].b,c=state[s].c;
if(f[pre][s][0][k]) {
if(mp[i][j]=='#') {
if(a!=j&&b!=j&&c!=j)f[now][s][0][k]+=f[pre][s][0][k];
continue;
}
f[now][s][0][k]+=f[pre][s][0][k];
if(a==j)f[now][id[0][b][c]][1][k]+=f[pre][s][0][k];
else if(b==j)f[now][id[a][0][c]][1][k]+=f[pre][s][0][k];
else if(c==j)f[now][id[a][b][0]][1][k]+=f[pre][s][0][k];
else if(k<3)f[now][id[j][b][c]][0][k+1]+=f[pre][s][0][k]; //新插头
}
if(f[pre][s][1][k]&&mp[i][j]=='.') {
if(a==j||b==j||c==j)continue;
f[now][s][0][k]+=f[pre][s][1][k]; //结束插头
f[now][s][1][k]+=f[pre][s][1][k];
}
}
}
Clear(f[now],1);
}
printf("%lld\n",f[now][1][0][3]);
return 0;
}
姥爷们赏瓶冰阔落吧~