URAL 1152 False Mirrors 搜索|记忆化搜索|状压

n个阳台，每个阳台上有怪物，第一个阳台跟最后一个相邻，每次攻击其中一个阳台，那么相邻的两个也会被破坏掉，但是你攻击一次，剩下的没有被消灭的怪兽就会攻击你，问消灭所有怪兽 所受伤害值最少是多少

一开始就想到了DFS，于是写了一发，居然超时了，然后看到n只有20，于是想到了状态压缩+记忆化搜索，还是比较清晰的推起来，然后31ms过了，后来过了又去看了一下网上题解，呵呵，发现 dfs也是可以的，自己没写好，连基础的东西都忘了。。。

int n;

int nnum[20 + 5];

int dp[(1<<20) + 5];

void init() {
	memset(nnum,0,sizeof(nnum));
	memset(dp,-1,sizeof(dp));
}

bool input() {
	while(cin>>n) {
		for(int i=0;i<n;i++)cin>>nnum[i];
		return false;
	}
	return true;
}

int dfs(int ss) {
	if(dp[ss] != -1)return dp[ss];
	int now = 0;
	for(int i=0;i<n;i++) 
		if(ss &(1<<i)) now += nnum[i];
	int ret = inf;
	for(int i=0;i<n;i++) {
		int tmp = ss;
		int sum = 0;
		int cur = (i + n)%n;
		if(ss & (1<<cur)) {
			sum += nnum[cur];
			tmp ^= (1<<cur);
		}
		cur = (i + n + 1)%n;
		if(ss & (1<<cur)) {
			sum += nnum[cur];
			tmp ^= (1<<cur);
		}
		cur = (i + n - 1)%n;
		if(ss & (1<<cur)) {
			sum += nnum[cur];
			tmp ^= (1<<cur);
		}
		if(tmp == ss)continue;
		ret = min(ret,dfs(tmp) + now - sum);
	}
	return dp[ss] = ret;
}

void cal() {
	dp[0] = 0;
	int ans = dfs((1<<n) - 1);
	cout<<ans<<endl;
}

void output() {

}

int main() {
	while(true) {
		init();
		if(input())return 0;
		cal();
		output();
	}
	return 0;
}

URAL 1152 False Mirrors 搜索|记忆化搜索|状压

原文：http://blog.csdn.net/yitiaodacaidog/article/details/44563263