※ 引述《SHBK (頭腦好鈍 唉)》之銘言：
: ※ 引述《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
我知道可以用推的,我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