網頁

2014年4月20日 星期日

UVa 10944 Nuts for nuts..

想法:
    狀態壓縮DP題目,假設Larry編號為0,堅果編號從1~N,一開始先將任兩點距離算好,因為移動是八個方向,所以dis[i][j] = max(|x[i]-x[j]|, |y[i]-y[j]|)。
    接下來做dynamic programming,定義dp[i][j]這個矩陣用來存最短步數:
  • i為該狀態最後收集到的堅果編號
  • j表示該狀態
    狀態的表示是用二進位,例如有5個堅果,若j=22則二進位為10110,表示編號2,3,5號的堅果已經被收集過了。那麼dp[3][22]就是在2,3,5號堅果已經收集且3號堅果是最後被收集的最短步數。
    定義完成後,首先先將dp初始化成INF,然後對於dp[i][1<<(i-1)]初始化成dis[0][i],因為dp[i][1<<(i-1)]就是從起點走到編號i堅果的最短步數。然後以上面例子繼續,5個堅果,從狀態0 (00000)開始,一直遞增枚舉到狀態((1<<N)-1) (11111)就算完成。
    每次枚舉一個狀態i,例如10110,已經被收集的堅果編號j(也就是2,3,5);沒有被收集的堅果編號k(也就是1,4),然後再用迴圈跑這些已經被收集的編號j,每次就以這個編號j為最後被收集的編號(也就是dp[j][i]),加上j到k的距離去更新dp[k][i+ (1<<(k-1))]。整個式子
        dp[k][1+ (1<<(k-1))] = min(dp[k][1 + (k-1))], dp[j][i] + dis[j][k]);
   
    最後在檢查dp[1~5][11111]+dis[1~5][0](記得要走回原點)哪一個最小就是答案。

另外<<這個運算符的順序很低,所以括號要記得加。




沒有留言:

張貼留言