xhSong's Blog

发现自己好久好久没有写点东西了。呵呵！……

今天做了下hdu3475http://acm.hdu.edu.cn/showproblem.php?pid=3475，自己用了一种比较诡异的方法，没想法跑到了第一，以62ms的速度领先于第二名（281ms）。于是再这里和大家分享一下。

题目大意：

有一个n*m（1<=n<=100, 1<=m<=10）的矩阵，每一个格子有一盏灯，对于每一盏灯，要不就是开着要不就是关着，现在要你把所有的灯都关掉，每一次操作可以改变每一盏灯的状态（关到开，开到关），问最少要操作几次。对于每一盏灯和他相邻的8盏灯都有可能存在连线。当你改变一盏灯的状态的时候，和他有直接相连的灯都会改变状态。

题目分析：

当然这个题目可以同解方程的方法去做，但是好像时间复杂度过不去，我数学是个菜鸟，不好说多少。

还是讲讲我的方法吧。从题目的数据范围上看，m最多只有10，那就是状态压缩dp了，用2^m个状态表示某一行的灯的状态。但是由于改变某一行中一个灯的状态，可能影响它上一行等的状态，也可能影响下一行的状态，这样，我们至少要记录两行的状态才能进行转移。于是，我们定义数组dp[i=100][state1=1024][state2=1024]，来表示第i行以后，第i行的状态为state1，第i+1行的状态为state2，第1至i-1行的状态均为0（所有的灯都关着）的最少操作数。计算一下会发现这样的dp数组肯定是会内存的，所以是要用滚动数组的。

状态转移的时候，用2^m枚举第i+1行的那些灯是进行过操作的（很显然一个灯是不会进行一次以上的操作的），然后进行转移，转移时一定要注意，对第i+1行操作后，第i行灯的状态一定要是全部关掉的。这里完全可以先枚举第i+1行的状态，在根据第i+1行对第i行灯的影响，去确定第i行灯的状态。这样总的空间复杂度为O(2*2^20)，时间复杂度为(100*2^10*2^10)，可以看到，空间能过得去，但是时间复杂度貌似还是有点勉强的，已经到了10^8。

其实有很多状态都是不可能的，能不能在转移的时候不出现这些状态？于是有了诡异的想法，就是把状态数组的最后一维改成链表，这样，枚举完第i+1行的操作状态后，直接对第i行能全部变成0的状态进行转移，这些都是合法的状态。其实这样做的理论复杂度还比原先方法还高，应为在链表中插入一个元素的时候是要遍历整个链表的，但由于链表元素比较少，真实的效果还是很好的。

这种方法再用于dp数组中合法状态很稀疏的情况还是比较好的，其他情况最会更慢。

/* 
 * File:   hdu-3475.cpp
 * Author: hust_boys
 * Created on 2010年10月31日, 上午10:23
 */

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define maxsize (1<<10)
using namespace std;

struct Node {
	int to, step;
	Node *next;
} t[2][maxsize * maxsize], *child[2][maxsize];
//链表的元素定义，child相对于dp数组，第一维为2，用于滚动，t数组作为节点池 
 
int street, cnt, n, m, state[101], cp[101][10], cn[101][10], cs[101][10];
//street： 当前处理到的行数
//n，m：行列数
//state：每一行状态压缩后的数值
//cp：第i行，第j列（i从1开始，j从0开始）的灯，对上一层灯的影响，压缩值
//cn： 第i行，第j列的灯，对下一层灯的影响，压缩值
//cs：第i行，第j列的灯，对当前一层灯的影响（包括自己），压缩值 

//插入元素，即状态转移 
void insert(int x, int to, int step) {
	int have = 0, now = street % 2;
	for (Node *p = child[now][x]; p; p = p->next) {
		if (p->to == to) {
			p->step = min(p->step, step);
			have = 1;
			break;
		}
	}
	if (!have) {
		t[now][cnt].to = to, t[now][cnt].step = step;
		t[now][cnt].next = child[now][x];
		child[now][x] = &t[now][cnt++];
	}
}

//dfs产生当前行的状态 
void DFS(int k, int now, int pre, int next, int s) {
	if (k == m) {
		for (Node *p = child[(street - 1) % 2][pre]; p; p = p->next) {
			insert(p->to ^ now, next, p->step + s);
		}
		return;
	}
	DFS(k + 1, now, pre, next, s);
    //不改变第k个的状态 
	DFS(k + 1, now ^ cs[street][k], pre ^ cp[street][k], next ^ cn[street][k], s + 1);
	// 改变第k个的状态 
}

int solve() {
    //初始化 
	cnt = street = 0;
	memset(child[0], 0, sizeof (child[0]));
	insert(0, 0, 0);
	//dp 
	int now;
	for (street = 1; street <= n; ++street) {
		now = street % 2;
		memset(child[now], 0, sizeof (child[0]));
		cnt = 0;
		DFS(0, state[street], 0, 0, 0);
	}
	//获得结果 
	int res = -1;
	for (Node *p = child[now][0]; p; p = p->next) {
		if (p->to == 0) {
			if (res == -1) {
				res = p->step;
			} else {
				res = min(res, p->step);
			}
		}
	}
	return res;
}

void input() {
	char s[30];
	scanf("%d%d", &n, &m);
	gets(s);
	memset(state, 0, sizeof(state));
	memset(cn, 0, sizeof (cn));
	memset(cp, 0, sizeof (cp));
	memset(cs, 0, sizeof (cs));
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < m; ++j) {
			cs[i][j] = 1 << j;
		}
	}
	for (int i = 1; i < n * 2; ++i) {
		gets(s);
		if (i % 2) {
			int now = i / 2 + 1;
			for (int j = 0; j < m; ++j) {
				if (s[j * 2] == 'o') {
					state[now] |= 1 << j;
				}
			}
			for (int j = 1; j < m; ++j) {
				if (s[j * 2 - 1] == '-') {
					cs[now][j - 1] |= 1 << j;
					cs[now][j] |= 1 << (j - 1);
				}
			}
		} else {
			for (int j = 0; j < m; ++j) {
				if (s[j * 2] == '|') {
					cn[i / 2][j] |= 1 << j;
					cp[i / 2 + 1][j] |= 1 << j;
				}
			}
			for (int j = 1; j < m; ++j) {
				if (s[j * 2 - 1] == '/') {
					cn[i / 2][j] |= 1 << (j - 1);
					cp[i / 2 + 1][j - 1] |= 1 << j;
				} else if (s[j * 2 - 1] == '\\') {
					cn[i / 2][j - 1] |= 1 << j;
					cp[i / 2 + 1][j] |= 1 << (j - 1);
				} else if (s[j * 2 - 1] == 'X') {
					cn[i / 2][j] |= 1 << (j - 1);
					cp[i / 2 + 1][j - 1] |= 1 << j;
					cn[i / 2][j - 1] |= 1 << j;
					cp[i / 2 + 1][j] |= 1 << (j - 1);
				}
			}
		}
	}
}

int main(int argc, char** argv) {
	int T;
	scanf("%d", &T);
	for (int test = 1; test <= T; ++test) {
		input();
		int res = solve();
		printf("Case %d: %d\n", test, res);
	}
	return 0;
}