「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$）。
右插头可以向右延续，也可以直接断掉。

---

代码

#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;
}