※ 引述《kc655039 (￾NN￾N ￾  )》之銘言： : ※ 引述《SHBK (頭腦好鈍 唉)》之銘言： : : 這一題用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.. 10237 我還沒解 861我跑的時間是0.014 我想你的演算法沒有問題 要快的話 就要用C寫(cin 改成 scanf 這裡會快不少) 還有你有function call呼叫當然會比較慢囉(我是都寫在main裡) 每次輸入就把最大的n存起來(max) 下一次n<max 直接查表就好 所以用兩個array存兩種顏色的組合數(有初始化) 大概降子就會快很多了 : 也許這些數字沒什麼意義吧,但是ghost 77的就顯然寫的比較好^^ : 請教一下你們寫這題的時候有做這種事情嗎:long long result[N][M]={0}; : 就是把存放最後結果的array初始化. : 還有就是大家開了一些什麼array? : 真的滿想了解到底慢在哪邊,因為其實我都想過要省下時間, : 但成績出來就是不好看... -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.140.79.125