首页 > 代码库 > 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)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。