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