Brief description :

给定一块 n × m 的电路板，上面有一些位置是坏的，问最多可以镶嵌多少2 × 3大小的芯片。
（1 < = n <= 150, 1 <= m <= 10 …）

Analyse :

…

#include <iostream>
using namespace std;
const int hh = 150, ww = 10, _W = 16, ss = 1123; //1 << 20; //?
const int _A = (1 << ww) - 1, _B = _A << _W;
int O[hh+1];
int h, w, s0, s1, s2, up;
short ans, b;

struct hashTable {
	int state[ss], head[ss], next[ss], sz;
	short key[ss];
	
	inline void clear() {
		sz = 0;
		memset(head, -1, sizeof(head));
	}
	inline void insert(int s0, int s1, short val) {
		int s = s0 | s1 | s1 << _W;
		int x = s % ss;
		for ( int it = head[x] ; it != -1 ; it = next[it] ) {
			if ( state[it] == s ) {
				key[it] = max(key[it], val);
				return;
			}
		}
		state[sz] = s, key[sz] = val;
		next[sz] = head[x];
		head[x] = sz++;
	}
	inline short search(int s){
		int x = s % ss;
		for ( int it = head[x] ; it != -1 ; it = next[it])
			if ( state[it] == s ) return key[it];
		return 0;
	}
} H[2] , *src , *des;


void dfs(int j, short d, int s1, int s2){
	while (true){
		if (j == w){
			des->insert(s1, s2, b + d);
			return;
		}
		else {
			if (j < w-2 && !(s0 & 7 << j))
				dfs(j+3, d+1, s1 | 7 << j, s2);
			if (j < w-1 && !(s0 & 3 << j) && !(s2 & 3 << j))
				dfs(j+2, d+1, s1, s2 | 3 << j);
		}
		j++;
	}
}


void solve(){
	src = H, des = src + 1, des->clear(), des->insert(O[0], O[1], 0);
	
	for (int i = 0; i < h - 1; i ++){
		swap(src, des), des->clear(), s2 = O[i+2];
		for (int it = 0; it < src->sz; it++){
			s0 = src->state[it] & _A | up, s1 = (src->state[it] & _B) >> _W;
			b = src->key[it], dfs(0, 0, s1, s2);
		}
		//cout << des->sz << endl;
	}
	
	ans = 0;
	for (int it = 0; it < des->sz; it++)
		ans = max(ans, des->key[it]);
}

void init(){
	int t;
	scanf("%d%d%d", &h, &w, &t); 
	memset(O, 0, sizeof(O));
	
	int x, y;
	for (int i=0;i<t;i++){
		scanf("%d%d", &x, &y), x--, y--;
		O[x] |= 1 << y;
	}
	
	up = 1 << w;
	O[h] = up - 1;
}


int main(){
	//freopen("in.txt", "r", stdin);
	int T; cin >> T;
	while (T--){
		init(); solve();
		cout << ans << endl;
	}
}

External link :

http://poj.org/problem?id=1038

Posted by xiaodao
Category: 日常