xhSong's Blog

留着待查http://qing.weibo.com/1460499910/570d75c633001aav.html

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

今天做了下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;
}

概率加DP一直是自己的弱项，于是找了两个这样的题目来做。

http://acm.hdu.edu.cn/showproblem.php?pid=2955

http://acm.hdu.edu.cn/showproblem.php?pid=1203

这两个还都算是比较水的题目，在这提一下就是了。

1203：用f[i][j]表示前i个学校用j万美元申请费，不能获得offer的最小概率，当然f数组是double类型的，则初始化为f[][]=1;状态转移方程为

当然，这个题目用滚动数组会很方便。

2599：网上有人说把概率放大，做为容量，把钱数作为价值来进行背包。我觉得只是不恰当的。这个题目应该把钱数做为容量进行背包：

f[i][j]表示在前i个bank，抢劫j个单位的钱都逃走的最大概率。初始化f[][] = 0, f[0][0] = 1;状态转移方程为

同上，这个题目用滚动数组亦比较方便。

http://acm.hdu.edu.cn/showproblem.php?pid=3376

题目大意： 在一个n*n(n <= 600)的方格图中有些1 到100的数，一个人从左上角出发，可以向下走一格，也可以向下走一格，直到走到右下角。然后返回到左上角，返回的时候不能经过走过的位置。走过某一个格子的时候可以取走格子里面的数。求取到数的和最大值。
其实这个题目以前就看过，但是没有认真去想。今天baidu了一下的。得到的基本思路都是差不多的，都是多线程动态规划，这里有这篇比较好的：

http://www.redswallowz.com/bbs/read.php?tid=2827

但我感觉换一种表示状态可能会更好一点。 我用f[x1][y1][x2]来表示状态。f[x1][y1][x2]表示一个线程在点(x1, y1)，另一个在点(x2, x1 + y1 - x2)时，所能获得的最大和。则：
f[1][1][1] = map[1][1];
f[x1][y1][x2] = max{f[x1 - 1][y1][x2 - 1], f[x1 - 1][y1][x2], f[x1][y1 - 1][x2 - 1], f[x1][y1 - 1][x2]} + map[x1][y1] + map[x2][x1 + y1 - x2] | x1 < x2;

这样的循环变量的范围会好控制点。

对于时间复杂度而言虽然都是O(n^3)的，但是后面一种方法常数会稍微的小一点。其实今天rp还算是比较好的。解题报告上说是用网络流（这里就不讨论这种方法，感兴趣的同学自己查资料）ms是O(n^2)的复杂度，但是我用O(n^3)优化了很久（用C++ TLE了，用C AC了）的DP照样过了，这小常数可是功不可没呀！

对于空间复杂度来说，虽然都是O(n^3)，但前面的一种表达的常数是2，这个常数是1。其实就这个题目而言你是非用滚动数组不可的，不然肯定MLE。对于滚动数组，可能有些人不知道，其实很简单。就是我在算f[x1][y1][x2] 的时候只会用到f[x1 - 1][][]和f[x1][][]的数据，f[1 to x1 - 2][][]都是没有用的，这样很自然的就能想到，我用f[2][n][n]来代替f[n][n][n]。我用f[0][][]和f[1][][]交替表示f[x1 - 1][][]和f[x1][][]。这样就能达到将空间复杂度降到O(n^2)。

一下是这种方法的核心代码：
 

memset(f, 0, sizeof(f));
f[1][1][1] = map[1][1];
now = 1, last = 0;
for(x1 = 2; x1 <= n; ++ x1) {
    for(y1 = 1; y1 < n; ++ y1) { 
        for(x2 = max(1, x1 + y1 - n); x2 < x1; ++ x2) { 
            f[now][y1][x2] = max(f[last][y1][x2 - 1], f[last][y1][x2], f[now][y1 - 1][x2 - 1], f[now][y1 - 1][x2]) + map[x1][y1] + map[x2][x1 + y1 - x2]; 
        }
    }
}
ans = f[n % 2][n - 1][n -1] + a[n][n];