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

流浪中的灰原立

流浪云's ACM && 灰原立's 生活

 
 
 

日志

 
 

细节决定成败  

2007-03-09 01:59:07|  分类: ACM技术相关 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

今天做POJ 1156 A STRIP OF LAND ,是IOI 1999的题目 (注:IOI=国际青少年信息学奥林匹克),一道比较经典的DP,完全靠自己想出一种O(u*v*c*100)的算法,再加上最优性剪枝,最后以较快的速度通过,无比满足~~~这道算是比较有算法性的题目,也是自己这么久以来过的较有意义的一道,而且没有偷看任何解题报告,完全自己动手,自食其力,这种感觉真是爽啊~~~我要继续努力,重拾旧梦~~~!!

此外写一下这道题的一点感想。这题的DP不加剪枝是TLE的,后来加了一个最优性剪枝,即“倘若按当前情况发展,考虑最好的情况,也不可能比现有的较有解更优,就可以剪去当前情况,不必再讨论”。于是我的程序里有这么一行: if ( totl * min < ans ) break ;  其中的ans是至今找到的最优解,而min是当前情况,min*totl是当前情况发展下去的最理想结果,如果这个还比当前的最优解ans差,则可以break掉。这样修改后,可以通过了,不过速度比较慢:rovingcloud 1156 Accepted 23292K 14480MS

后来想继续优化,尝试过几个新剪枝,可也只是徒劳。即再也想不到更好的剪枝了。此时想放弃了,想去看看解题报告或其它人的方法。正准备关掉自己的程序时,还是不肯死心,想再在一些代码上做点小优化,突然想到把上面的“<“改成”<=“试试,即 if ( totl * min <= ans ) break ;   提交,刷新,奇迹居然发生了:

rovingcloud 1156 Accepted 23292K 3497MS

太神奇了!不过是加一个“=“号!居然可以快这么多!也就是由原来的 ”最理想结果也比当前最优解差“ 变成 ”最理想结果也不会比当前最优解更优” 后,速度就有了明显的进步。只是一个小细节啊!之前还认为是无关痛痒的地方,结果居然会影响这么大!有道是,细节决定成败!

  评论这张
 
阅读(324)| 评论(2)
推荐 转载

历史上的今天

评论

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

页脚

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