UVA 690 Pipeline Scheduling (搜索+位运算+剪枝）

690 - Pipeline Scheduling

思路：利用位运算保存每个通道的放置方法，然后去深搜，要加剪枝。详细见代码

代码：

#include <stdio.h>
#include <string.h>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
const int N = 35;
int n,p[5],ans,w[N],wn;
char str[N];

bool judge(int s0,int s1,int s2,int s3,int s4) {
	return ((s0&p[0]) == 0 
		&& (s1&p[1]) == 0 
		&& (s2&p[2]) == 0 
		&& (s3&p[3]) == 0 
		&& (s4&p[4]) == 0);
}

void init() {
	ans = 10 * n; wn = 0;
	for (int i = 0; i < 5; i++) {
		p[i] = 0;
		scanf("%s",str);
		for (int j = n - 1; j >= 0; j--) {
			p[i] = p[i] * 2 + (str[j] == 'X');
		}
	}
	int s0 = p[0],s1 = p[1],s2 = p[2],s3 = p[3],s4 = p[4];
	for (int k = 0; k <= n; k++) {
		if (judge((s0>>k),(s1>>k),(s2>>k),(s3>>k),(s4>>k))) {
			w[wn++] = k;//剪枝，开w数组把不能放的位置剔除掉
		}
	}
}

void dfs(int s0,int s4,int d,int len) {
	if (len + w[0] * (10 - d) > ans) return;//关键剪枝
	if (d == 10) {
		ans = min(ans,len);
		return;
	}
	for (int i = 0; i < wn; i++) {
		int ss0 = (s0>>w[i]),ss1 = (s1>>w[i]),ss2 = (s2>>w[i]),ss3 = (s3>>w[i]),ss4 = (s4>>w[i]);
		if (judge(ss0,ss1,ss2,ss3,ss4)) {
			dfs(ss0^p[0],ss1^p[1],ss2^p[2],ss3^p[3],ss4^p[4],d + 1,len + w[i]);
		}
	}
}

int main() {
	while (~scanf("%d",&n) && n) {
		init();
		dfs(p[0],p[1],p[2],p[3],p[4],1,n);
		printf("%dn",ans);
	}
	return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!