noip教程動態(tài)規(guī)劃ppt課件-展示頁
2025-05-14 18:18本頁面
【正文】 者比后者大，那么這對數(shù)就是一個逆序?qū)Α討B(tài)規(guī)劃 陳爽 ? 為了解決一類最優(yōu)化問題 ? 通過求得所有子問題的最優(yōu)解來得到最終問題的最優(yōu)解 動態(tài)規(guī)劃 ? 狀態(tài) ? 狀態(tài)轉(zhuǎn)移方程 ? 初始條件 動態(tài)規(guī) 劃的基本要素 ? 線性動態(tài)規(guī)劃 ? 區(qū)間動態(tài)規(guī)劃 ? 狀態(tài)壓縮動態(tài)規(guī)劃 ? 樹形動態(tài)規(guī)劃 動態(tài)規(guī) 劃的分 類 ? 狀態(tài)是一維的 ? F[i] 由 F[j] (ji) 得到 ? 初始條件 F[0] 或 F[1] Part 1 線性動態(tài)規(guī)劃 ? 設(shè)有整數(shù)序列 b1,b2,b3,… ,bm，若存在下標(biāo)i1i2i3 … in，且 bi1bi2bi3 … bin，則稱 b1,b2,b3,… ,bm中有長度為 n的上升序列 bi1 , bi2 ,bi3 ,… ,bin 。 ? 求最長上升序列的長度 N ? 求長度為 N的上升序列的個數(shù) ? 求本質(zhì)不同的長度為 N的上升序列的個數(shù) ? N=1000 例 ? 狀 態(tài) ：F[i]表示以 b[i]結(jié) 尾的最 長 上 升 序列 長 度 ? 轉(zhuǎn) 移方程： F[i]=max(F[j]+1),jI,b[j]b[i] ? 初始條件： F[i]=1, 1=i=N ? T[i]表示以 b[i]結(jié) 尾的 序列長度為 F[i]的方案數(shù) ? T[i]=sigma(T[j]), F[i]=F[j]+1, B[i]B[j] ? 初始條件： T[i]=1 Solution ? 本質(zhì)不同？ ? Order[i]表示 B[i]在序列 B中是第幾大的 ? T[i]=sigma(T[j]), 當(dāng)某個 order[j1]=order[j2]時，只累加一個 ? 時間復(fù)雜度： O(N^2) ? 空間復(fù)雜度 ： O(N) Solution ? P[i] 表示上身序列 長 度 為 i的序列末尾元素的最小 值 ? 當(dāng) 計 算 F[i]時 ，二分 j，滿 足 P[j]B[i] ? F[i]=F[j]+1 ? P[F[i]]=min(P[F[i]], B[i]) ? 時間 復(fù) 雜 度： O(NlogN) LIS O（NlogN）算法 ? 考慮一個由 N個整數(shù)構(gòu)成的數(shù)列，其中 1到 N都在數(shù)列中出現(xiàn)了恰好一次。而整個數(shù)列的逆序數(shù)就是其中所有逆序?qū)Φ目倲?shù)。 ? 寫一個程序，計算有多少長度為 N的這種數(shù)列，使它的逆序數(shù)恰為 C。 例 3. Mod 4 余數(shù)最小 問題 2 3
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1