摘要: 參考了下別人的代碼，dp真是千變?nèi)f化??！
這與搬寢室還是有很大不同的，要倒過來做；
dp[物品組數(shù)][物品個數(shù)](I為I副筷子，J為總共筷子)
現(xiàn)在轉入正題,這個題目要求每一組有3個筷子,前2個的差的平方最小,
首先和前面題目一樣先排序對把,顯然從大到小排(因為這樣完全可以轉化成搬寢室 那個一樣的思想)
比如取第2隊物品,那么第一對已經(jīng)取完保存在數(shù)組里面了,
那么從s[2][3*2+1]計算到s[2][n],
為什么這樣就可以呢?
仔細想下,第2組,前面只要有2個可以作為最大的筷子了,一定滿足題目意思的了,所以一直計算下去,
狀態(tài)轉移方程和前面一樣~
dp[i][j]=min(dp[i-1][j-2]+(a[j]-a[j-1])*(a[j]-a[j-1]),dp[i][j-1]);
ps:排序從大到小很精妙~
閱讀全文