noip教程動態(tài)規(guī)劃ppt課件-閱讀頁
2025-05-20 18:18本頁面
【正文】 。不考慮它的空子樹。 Solution ? 注意到任意一棵子樹的中序遍歷一定是一段 連續(xù) 的區(qū)間 ? 枚舉區(qū)間中的第幾個元素作為這一段區(qū)間的根 ? 記 f[i][j]表示中序遍歷為 [i,j]這個區(qū)間的子樹的最大分數(shù)， g[i]表示第 i個點的分數(shù) ? F[i][j]=max(F[i][k1]*F[k+1][j]+g[i]) ? 初始條件： F[i][j]=0 Solution ? 給你一個矩陣，其邊長均為整數(shù)。切割工作由一臺切割機器完成，它能沿平行于矩形任一邊的方向，從一邊開始一直切割到另一邊。 ? 矩形邊長小于等于 100 例 7. 矩形 分割 問題 ? F[i][j]表示長為 i寬為 j的矩形所需的最小正方形個數(shù) ? F[i][j]=min(F[i][k]+F[i][jk],F[k][j]+F[ik][j]) Solution ? 見外部題目描述 例 8. psolve ? 狀態(tài)： F[i][j]表示 i～ j在一個月做完的最小所需月份 ? 枚舉上一個做了 k～ i1 ? 轉(zhuǎn)移方程： F[i][j]=min(F[k][i1]+1), s1[i][j]+s2[k][i1]=P, 且 F[k][i1]合法 ? 初始條件： F[0][0]=1 ? 此題寫起來有好多小細節(jié)，建議練習代碼 Solution ? 動態(tài)規(guī)劃問題具有以下基本特征 ： ? 問題具有多階段決策的特征。 ? 每一階段都面臨一個決策，選擇不同的決策將會導致下一階段不同的狀態(tài)。 動態(tài)規(guī)劃的基本模型 ? 狀態(tài)壓縮是一種非常暴力的動態(tài)規(guī)劃，特征也非常明顯，一般適用于 數(shù)據(jù)規(guī)模較小 的情況。 ? 所謂狀態(tài)壓縮，就是把一個比較復(fù)雜的狀態(tài)壓縮為一個數(shù)，通常采用某一種進制的表示方法 ? 經(jīng)常通過記憶化搜索來實現(xiàn) Part 3. 狀 態(tài)壓縮動態(tài)規(guī) 劃 ? 放寒假了，小 D終于可以回家了。 小 D的背包可以被看作一個 4行 N列的矩陣，每個物品放入背包的物品恰好需要占據(jù)兩個相鄰的方格，任意兩個物品不能占據(jù)相同的方格。 現(xiàn)在小 D想知道，不同的放置方案數(shù)有多少種。 ? 通過枚舉第 k列骨牌的放置方案，不難得到從 F[k][u]（ u = 0 ? 15 ）到 F[k+1][v]（ v = 0 ? 15 ）的轉(zhuǎn)移方程。 Solution ? L盞燈，每盞燈為 0/1，表示亮的或暗的 ? 有一個叉子有 T個叉尖，相鄰兩個叉尖的距離等于相鄰兩盞燈的距離
教學課件相關(guān)推薦
鄂ICP備17016276號-1