作者SHBK (头脑好钝 唉)
看板ACMCLUB
标题Re: [问题] 861
时间Wed Aug 31 12:47:59 2005
※ 引述《kc655039 (NNN  )》之铭言：
: 我解开但是怎麽更快呢,我是指用Backtracking,
: 我的作法是,如果把斜线分成偶数和奇数条,偶数不会撞到奇数,
: 再分开找出放k个棋子分别放在偶数条斜线和积数条斜线各有几种方法,
: 接下来就用 k个棋子中放在偶数条斜线上的*(k-放在偶数条斜线上的)的总和,
: 就求出k个棋子放在棋盘上的解法,然後分别从其盘是2求到八,
: 棋盘大小是1的时候我是直接把答案放到结果table里面,
: 这就是作法了......(希望能够被理解),
: 目前觉得应该可以推出来,就是不用暴力找解,
: 但实在很好奇就是.....我的backtracking总是没办法到最快.
: 所以想请大家如果也是使用backtracking解出来的....看看有没有什麽地方,
: 是很特别巧思.....可以给我参考参考
: 我把我的code贴在下方(如果不可以这样可以跟我说一声):
这一题用backtracking 会很慢..即使有bounded条件也没快多少
这题要用DP去做 会超快...
http://www.csie.nctu.edu.tw/~chchu/phpBB/viewtopic.php?t=354
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 218.163.135.5