注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 5113 Black And White  

2014-12-02 19:29:14|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=5113
K种颜色涂满N*M的矩阵,要求相邻的颜色不能一样,问可行解。
这题是2014北京现场赛的B题,这题在封榜后才开,一看就上了dfs,没加剪枝T了一发,然后想各种剪枝,想到如果有某种颜色数量大于剩余格子数量的一半,则return,加上后还是T,又是各种改,继续T……
T得不行了,然后发现也可以构造,YY了一种构造方法,打完后发现解法不是通解,有特殊情况,最后就是各种改,各种交,到比赛结束也没有过……
赛后现场题解说,这题dfs和构造都可以,而且方法和我的竟然都是一样,顿时一种崩溃的感觉……
之后等题目重现开出来后,发现剪枝是想到了,但是用的不对……
之前是一边搜索一边判断剪枝,这样有些不符合条件的状态会每个搜一遍,浪费很多时间,
正确姿势应该是在搜索之前先循环判断一遍,是否这种状态下会出现某种颜色数量超过剩余的一半,有就return。

int n,m,k,flag,f[32],r[10][10];

void Output()
{
pfs("YES");
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(j) pfk;
printf("%d",r[i][j]);
}
pfn;
}
}

int jud(int x,int y,int i)
{
if(x-1>=0 && r[x-1][y] == i)
return 0;
if(y-1>=0 && r[x][y-1] == i)
return 0;
return 1;
}

void dfs(int x,int y,int cnt)
{
if(flag) return ;
if(x == n)
{
flag=1;
Output();
return ;
}
for(int i=1;i<=k;i++) //先进行剪枝,然后进行下面的循环搜索,否则TLE
if(f[i]>(cnt+1)/2)
return ;
for(int i=1;i<=k;i++)
if(f[i] && jud(x,y,i))
{
r[x][y]=i;
f[i]--;
if(y+1 == m) dfs(x+1,0,cnt-1);
else dfs(x,y+1,cnt-1);
f[i]++;r[x][y]=0;
}
}


int main()
{
int T,cas=1;
sf(T);
while(T--)
{
printf("Case #%d:\n",cas++);
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=k;i++)
sf(f[i]);
MEM(r);flag=0;
dfs(0,0,n*m);
if(flag == 0)
pfs("NO");
}
return 0;
}


  评论这张
 
阅读(70)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017