首页 > 代码库 > Balanced Teams (USACO Jan Bronze 2014)

Balanced Teams (USACO Jan Bronze 2014)

既然是bronze,毫无压力的AC了.

就是个深搜,当然加个剪枝--最后一个组不用搜.

恩可以一个一个组分层次dfs,这样会跑得飞起~~也不容易错

#include <cstdio>int f[13],i,su,tt1,tt2,lev[4],min;bool has[13];inline int md(int a,int b,int c,int d){	tt1=a,tt2=a;	if(tt1<b)tt1=b;	if(tt1<c)tt1=c;	if(tt1<d)tt1=d;	if(tt2>b)tt2=b;	if(tt2>c)tt2=c;	if(tt2>d)tt2=d;	return tt1-tt2;}void dfs(int depth){	int i,j,k;	if(depth==3){		lev[3]=su-lev[0]-lev[1]-lev[2];		i=md(lev[0],lev[1],lev[2],lev[3]);		if(i<min) min=i;		return;	}	for(i=0;i<12;++i){		if(has[i]) continue;		has[i]=true;		for(j=i+1;j<12;++j){			if(has[j]) continue;			has[j]=true;			for(k=j+1;k<12;++k){				if(has[k]) continue;				has[k]=true;				lev[depth]=f[i]+f[j]+f[k];				dfs(depth+1);				has[k]=false;			}			has[j]=false;		}		has[i]=false;	}}int main(){	for(i=0;i<12;++i) scanf("%d",f+i),su+=f[i];	min=0x7fffffff;	dfs(0);	printf("%d\n", min);	return 0;}

  

Balanced Teams (USACO Jan Bronze 2014)