BZOJ2331 [SCOI2011]地板

插头DP的基础题。想插头DP都是将军没走的时候给我讲的了，距今有大半年了吧。mhy已经写了无数道了，我才开始写。唉，还是效率太低。

插头DP的意思是把已经处理的部分的轮廓线上对后面状态有影响的东西状压下来，然后挨着处理每个格子的状态（比如方向，或者这里的地板怎么铺之类的）。

具体到这道题来说，考虑一个相邻格子之前的边，那么它可能没有连接两个相同的磁砖，有可能连接了两个还没有拐过弯的磁砖，有可能连接了两个已经拐过弯的磁砖，一共是3种情况，所以用一个三进制数把它压下来。然后直接一路转移过去就行了。要注意的是每行都处理完了之后要把最边上的那一条从右移动到左，所以还需要把所有的状态都改一下。

今天效率比较低，心不在焉，然后在最后一个转移的地方wa了大半天。插头DP的调试也比较麻烦。所以我还是naive。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 13;
const int maxa = 109;
const int maxs = 200009;
const int mod = 20110520;

bool mp[maxa][maxa];
int n, m, a[maxn], b[maxn], f[2][maxs];

#define fc f[cur]
#define fp f[prv]
#define doNothing ;
inline void mInc(int&  _a_, int _b_) {
	_a_ += _b_;
	if (_a_ >= mod)
		_a_ %= mod;
}

void unzipStatus(int z, int* a) {
	for (int i = 0; i <= m; ++ i) {
		a[i] = z % 3;
		z /= 3;
	}
}
int zipStatus(int* a) {
	int s(0);
	for (int i = m; i >= 0; -- i)
		s = s * 3 + a[i];
	return s;
}

int plugDP() {
	int prv(0), cur(1), e(1);
	memset(f, 0, sizeof(f));
	fc[0] = 1;
	for (int i = 0; i <= m; ++ i)
		e *= 3;
	for (int i = 0; i < n; ++ i) {
		for (int j = 0; j < m; ++ j) {
			swap(cur, prv);
			for (int z = 0; z < e; ++ z)
				fc[z] = 0;
			for (int z = 0; z < e; ++ z)
				if (fp[z]) {
					unzipStatus(z, a);
					if (mp[i][j]) {
						if (a[j] == 0) {
							if (a[j + 1] == 0) {
								memcpy(b, a, sizeof(a));
								b[j] = b[j + 1] = 2;
								mInc(fc[zipStatus(b)], fp[z]);
								b[j] = 0;
								b[j + 1] = 1;
								mInc(fc[zipStatus(b)], fp[z]);
								b[j] = 1;
								b[j + 1] = 0;
								mInc(fc[zipStatus(b)], fp[z]);
							}
							else if (a[j + 1] == 1) {
								memcpy(b, a, sizeof(a));
								b[j] = 0;
								b[j + 1] = 2;
								mInc(fc[zipStatus(b)], fp[z]);
								b[j] = 1;
								b[j + 1] = 0;
								mInc(fc[zipStatus(b)], fp[z]);
							}
							else if (a[j + 1] == 2) {
								memcpy(b, a, sizeof(a));
								b[j] = 2;
								b[j + 1] = 0;
								mInc(fc[zipStatus(b)], fp[z]);
								b[j] = 0;
								mInc(fc[zipStatus(b)], fp[z]);
							}
						}
						else if (a[j] == 1) {
							if (a[j + 1] == 0) {
								memcpy(b, a, sizeof(a));
								b[j] = 0;
								b[j + 1] = 1;
								mInc(fc[zipStatus(b)], fp[z]);
								b[j] = 2;
								b[j + 1] = 0;
								mInc(fc[zipStatus(b)], fp[z]);
							}
							else if (a[j + 1] == 1) {
								memcpy(b, a, sizeof(a));
								b[j] = b[j + 1] = 0;
								mInc(fc[zipStatus(b)], fp[z]);
							}
							else if (a[j + 1] == 2) {
								doNothing
							}
						}
						else if (a[j] == 2) {
							if (a[j + 1] == 0) {
								memcpy(b, a, sizeof(a));
								b[j] = b[j + 1] = 0;
								mInc(fc[zipStatus(b)], fp[z]);
								b[j + 1] = 2;
								mInc(fc[zipStatus(b)], fp[z]);
							}
							else if (a[j + 1] == 1) {
								doNothing
							}
							else if (a[j + 1] == 2) {
								doNothing
							}
						}
					}
					else {
						if (a[j] == 0 && a[j + 1] == 0)
							mInc(fc[z], fp[z]);
					}
				}
		}
		swap(cur, prv);
		for (int z = 0; z < e; ++ z) 
			fc[z] = 0;
		for (int z = 0; z < e; ++ z) 
			if (fp[z]) {
				unzipStatus(z, a);
				if (a[m])
					continue;
				for (int j = m; j; -- j)
					a[j] = a[j - 1];
				a[0] = 0;
				fc[zipStatus(a)] = fp[z];
			}
	}
	return fc[0];
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif

	scanf("%d%d", &n, &m);
	bool rev(n < m);
	for (int i = 0; i < n; ++ i) {
		static char g[maxa];
		scanf("%s", g);
		for (int j = 0; j < m; ++ j)
			if (rev)
				mp[j][i] = (g[j] == '_');
			else
				mp[i][j] = (g[j] == '_');
	}
	if (rev)
		swap(n, m);
	printf("%d\n", plugDP());
}