noip教程動(dòng)態(tài)規(guī)劃ppt課件(參考版)
2025-05-08 18:18本頁(yè)面
【正文】 有些叉尖斷了，用 0表示，否則為1 ? 叉子對(duì)準(zhǔn)開(kāi)關(guān)，可以改變燈的狀態(tài) ? 已知初始燈的狀態(tài)和叉尖狀態(tài)，求叉尖操作的序列使得最后亮著的燈最少 ? L=50, T=7 例 ? 同一位置只可能操作一次 ? 可以從左到右依次操作 ? F[i][S]表示最后 T盞燈燈的狀態(tài)為 S時(shí)，前 i盞燈至少還亮著多少盞 ? S為一個(gè) T位二進(jìn)制， 0表示暗， 1表示亮 ? 枚舉是否在 iT+1~i+1操作，從而轉(zhuǎn)移到 F[i+1][K] ? 時(shí)間復(fù)雜度： O(L*2^T) Solution ? 一定要符合最優(yōu)化原理，即滿足最優(yōu)子結(jié)構(gòu) ? 可按照某一順序，從小到大求解 ? 從大到小求解可用記憶化搜索 ? 注意邊界條件 ? 轉(zhuǎn)移方程一定要清晰，不要漏情況 ? 狀態(tài)的意義一定要清晰 DP注意事項(xiàng) Thx～ Questions are wele ? 。這個(gè)過(guò)程需要另外寫(xiě)一個(gè)程序去枚舉才能完成。 例 9. 多米諾骨牌覆蓋 ? 搜索？ ? n很大，超時(shí)嚴(yán)重 ? 動(dòng)態(tài)規(guī)劃？ ? 如何表示狀態(tài)？ ? 注意到每一列最多只有 4行，每一個(gè)格子對(duì)下一行的影響只有 2種：下一行對(duì)應(yīng)的格子是否可以和當(dāng)前格子一起放進(jìn)一個(gè)物品 ? 狀態(tài)壓縮！ 0/1表示每個(gè)格子的狀態(tài)， 4位二進(jìn)制數(shù)表示一行的狀態(tài) Solution ? 用 F[k][S]來(lái)描述一個(gè)狀態(tài)，這個(gè)狀態(tài)表示已經(jīng)把矩陣的前 k1列全部放滿，并且第 k列的覆蓋情況為 S（ s為一個(gè) 4位二進(jìn)制數(shù)），此時(shí)的擺放方案數(shù)（注意，其實(shí)只有 S中 1的個(gè)數(shù)為偶數(shù)時(shí)狀態(tài)才有意義，更加深入的探討會(huì)發(fā)現(xiàn)需要使用的狀態(tài)很少）。為了充分的利用自己的背包，小 D希望背包的所有空間都放置了物品，也就是說(shuō)，背包中恰好放入了 2N個(gè)物品。一個(gè)學(xué)期之后他有太多的東西想帶回家。 ? 狀態(tài)壓縮復(fù)雜度通常情況下是是指數(shù)級(jí)的，編程復(fù)雜度也相對(duì)較大。 ? 每一階段的最優(yōu)解問(wèn)題可以遞歸地歸結(jié)為下一階段各個(gè)可能狀態(tài)的最優(yōu)解問(wèn)題，各子問(wèn)題與原問(wèn)題具有完全相同的結(jié)構(gòu)。 ? 每一階段都有相應(yīng)的 “ 狀態(tài) ” 與之對(duì)應(yīng)，描述狀態(tài)的量稱為 “ 狀態(tài)變量 ” 。對(duì)得到的矩形再分別進(jìn)行切割。你想把矩陣切割成總數(shù)最少的正方形，其邊長(zhǎng)也為整數(shù)。 ? 試求一棵符合中序遍歷為（ 1,2,3,?,n ）且加分最高的二叉樹(shù) tree。每個(gè)節(jié)點(diǎn)都有一個(gè)分?jǐn)?shù)（均為正整數(shù)），記第 j個(gè)節(jié)點(diǎn)的分?jǐn)?shù)為 di， tree及它的每個(gè)子樹(shù)都有一個(gè)加分，任一棵
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1