Welcome To SDIBT ACM-ICPC Online Judge

VIRTUAL JUDGE Recent Contest F.A.Qs Discuss Home ProblemSet Status Ranklist 2 Contest LoginRegister Exam
SDIBT Online Judge WebBoard
[ New Thread ]
Problem 2361 >> 2361dfs
wl10174102 @ 2013-07-28 12:17:34
[ Quote ] [ Edit ] [ Delete ] 1#
原以为是多重背包,后来发现背不对,就看USACO training才知道原来自己题意都理解错了。人家要的是能裁出的最多种类的所需木料,而自己理解的是能裁出的最多数量的所需木料。= = 贴一下人家的剪枝优化:
1、很容易就能注意到,由于每块rail的价值是相等的——也就是说切小的要比切大的来的划算。那么我们在搜索能否切出i个rail的方案是自然要选最小的i个rail来切。
2、经过一些实验可以发现,先切大的rail比先切小的rail更容易提前出解。同样,[先切小的board比先切大的board更容易提前出解?]{注:好像先切大的board要比先切小的更快}。
3、由于r最大可能是1023,但是rail长度的范围却只有0~128,这点提醒了我们有很多rail的长度会是相同的。所以我们要避免冗余,优化搜索顺序。若有rail[i+1]=rail[i],可以通过这种方法剪掉很多冗余的枝条则rail[i+1]对应的board一定大于等于rail[i]对应的board。。【我直接将相同的长度的木料删除,结果发现不对额。。】
相应的,如果board[i]=board[i+1],那么从board[i]切下的最大的rail一定大于等于从board[i+1]切下的最大的rail。
4、对于切剩下的board(无法再切下rail),统计一下总和。如果这个值大于board长度的总和减去rail长度的总和,一定无解,可以剪枝。这个剪枝最关键。【这个,我觉得他们说的过于绕口,其实就是,若当前剩余的木料大于完美切割剩余的木料,那接下来能得到的种类数肯定小于完美切割】
5、二分答案【这个就是将(1)用程序来完成】
6、其实在读入的过程中,如果rail[i] > max{board} 那么这个rail应该舍去 By Clarkok
[Top]  [Previous]  [Next]

HOME Back

한국어 中文 English
All Copyright Reserved 2008-2010 SDIBT TEAM
GPL2.0 2003-2010 HUSTOJ Project TEAM
Anything about the Problems, Please Contact Admin:admin