hdu2955,hud1203 概率+DP 两例
Ubuntu 12.04下设置笔记本成为wifi热点

hdu3475,hdoj3475解题报告

xhSong posted @ 2010年10月31日 21:19 in 动态规划(DP) with tags hdu3475 hdoj3475 Street Lamp 2010 ACM-ICPC Multi-University , 1821 阅读

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

今天做了下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;
}
  • 无匹配
  • 无匹配
Avatar_small
net worth 说:
2023年12月11日 16:13

Who is your favorite singer/actress/famous star? Their net worth can be found easily at idol net worth


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter