※ 引述《SHBK (头脑好钝 唉)》之铭言： : ※ 引述《kc655039 (￾NN￾N ￾  )》之铭言： : : 我解开但是怎麽更快呢,我是指用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 我知道可以用推的,我861用backtracking是000080的时间, 你的方法跟我用的差不多一模一样呢.....(之前有人把棋盘转四十五度角, 分两种颜色分别补格子补成长方形也解开了). 可是我刚刚用推的解开10237也才....000088..., 应该算是DP吧....连DP都比正常人慢到底怎麽回事????? 还有就是.....用那个DP的程式跑861其实是000064.. 也许这些数字没什麽意义吧,但是ghost 77的就显然写的比较好^^ 请教一下你们写这题的时候有做这种事情吗:long long result[N][M]={0}; 就是把存放最後结果的array初始化. 还有就是大家开了一些什麽array? 真的满想了解到底慢在哪边,因为其实我都想过要省下时间, 但成绩出来就是不好看... --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 218.161.19.42