摘要: 從后往前推可保證 第3根筷子比前2個長 遞推與 搬寢室 類似 容易超內(nèi)存
閱讀全文
摘要: 本題就是選取2k個數(shù)的平方差最小
具體實現(xiàn)
先排序 然后 把相鄰2個數(shù)的平方差存到數(shù)組中
接下來就是如何推DP式 （ 其實我也沒推出 別給和我講的 非常感謝他 ）
比如n個數(shù)為 已排序 1 2 3 4 8 10 45 211
令 i = 物品數(shù) j = 要選取的 k 對
令 j （ j 可當下標 ）指到 10 這里 如果10 包含在 k對中 那在 1 - j 范圍內(nèi) 與10相鄰的 只有8 ，此時已選出一對 ，所以 還要從 i - 2個里面選出j - 1對, 不要忘了+已選出的那對
如果10 不包含在 k對中 那就要從 i - 1 里選出j對 。因為 目的是選出最優(yōu)解 當然還得選出最小的
已經(jīng)夠詳細的了 多來踩踩
閱讀全文