連結：UVa10271 chopsticks
題目：
在中國，人們用筷子來夾取食物吃，而劉先生家是個特例
他喜歡一個人發3支筷子，其中最長的用來當叉子
剩下兩支的長度希望能愈相近愈好，畢竟他們要湊成一雙筷子
而叉子的長度並不重要，只要確保他是3支裏頭最長的就好
這兩支較短的長度若分別是A, B，則會帶來(A-B)^2的不良感
今天有K+8個人，和至少3*K+24支筷子，請你找出最佳分發筷子的方法，使所有人得到的不良感總和最少
做法：
題目給的長度是已排序的
可以發現到，若要保持長度差平方盡量小，第i支筷子不是跟第i-1支就是跟第i+1支一組
但難點在於怎麼留下一支較長的筷子
如果從小開始取，則遇到的筷子是愈來愈長的，難以直接判定有沒有足夠多的"長筷子"當叉子
所以，換個邊，從最長的往最短的取，發現如果我們要取當前的筷子，只要前面三三一組後還有剩，就可以拿來當作叉子，畢竟剛剛那些都是比較長的，就可以列出轉移式
dp[i][j] = 前j支筷子分給i個人的最少不良感總和
if (j-2)-3*(i-1) <= 0 前面沒有多餘的筷子
dp[i][j] = dp[i][j-1] 沒辦法取
else
dp[i][j] = min(dp[i][j-1], dp[i-1][j-2]+(a[j-1]-a[j])^2) 看取或不取哪個划算
code:
可以發現到，若要保持長度差平方盡量小，第i支筷子不是跟第i-1支就是跟第i+1支一組
但難點在於怎麼留下一支較長的筷子
如果從小開始取，則遇到的筷子是愈來愈長的，難以直接判定有沒有足夠多的"長筷子"當叉子
所以，換個邊，從最長的往最短的取，發現如果我們要取當前的筷子，只要前面三三一組後還有剩，就可以拿來當作叉子，畢竟剛剛那些都是比較長的，就可以列出轉移式
dp[i][j] = 前j支筷子分給i個人的最少不良感總和
if (j-2)-3*(i-1) <= 0 前面沒有多餘的筷子
dp[i][j] = dp[i][j-1] 沒辦法取
else
dp[i][j] = min(dp[i][j-1], dp[i-1][j-2]+(a[j-1]-a[j])^2) 看取或不取哪個划算
code:
沒有留言:
張貼留言