noip教程動態(tài)規(guī)劃ppt課件(編輯修改稿)
2025-06-01 18:18 本頁面
【文章內(nèi)容簡介】 . 石子合并 Example 貪 心 N=5， 石子數(shù)分別為 3 4 6 5 4 2 用貪心法的合并過程如下： 第一次 3 4 6 5 4 2得分 5 第二次 5 4 6 5 4得分 9 第三次 9 6 5 4得分 9 第四次 9 6 9得分 15 第五次 15 9得分 24 第六次 24 總分： 62 第一次 3 4 6 5 4 2得分 7 第二次 7 6 5 4 2得分 13 第三次 13 5 4 2得分 6 第四次 13 5 6得分 11 第五次 13 11得分 24 第六次 24 總分： 61 顯然，貪心法是錯誤的。 ? 用 data[i,j]表示合并第 i～ j顆石子的分值 ? 狀態(tài)： max[i,j] = max(max[i, k] + max[i + k, j – k] + data[i,k] + data[i+k, j–k]) (2=k=j) ? 初始條件： max[i,1] = 0 ? 狀態(tài)： min[i,j] = min(min[i, k] + min[i + k, j – k] + data[i,k] + data[i+k, j– k]) (0=k=j) ? 初始條件： min[i,0] = 0 ? 時間復(fù)雜度： O(N^2) Solution ? 在一條馬路上，有一排燈，一個小朋友要去關(guān)燈，如果燈沒有被關(guān)掉，就會每秒造成一定的損失。小朋友一開始在某一個位置，在他左邊和右邊分別有一些燈，給出這些燈和他的距離以及每個燈每秒會造成的損失，求一個方案使得損失最小，輸出最小損失。燈的個數(shù) =1000 例 5. 關(guān)燈 問題 ? 關(guān)掉的燈一定是一個連續(xù)的區(qū)間 ? 如果路過一個燈但是沒有去關(guān)掉它 ?? ? 設(shè) opt[i][j][0/1] 表示區(qū)間 [i,j]中的燈都被關(guān)掉之后的最小損失，最后一維表示小朋友的當(dāng)前位置 ? 轉(zhuǎn)移：考慮當(dāng)前的關(guān)燈操作 ? 時間復(fù)雜度： O(N^2) Solution ? 設(shè)一個 n個節(jié)點(diǎn)的二叉樹 tree的中序遍歷為（ l,2,3,?,n ），其中數(shù)字 1,2,3,?,n 為節(jié)點(diǎn)編號。每個節(jié)點(diǎn)都有一個分?jǐn)?shù)（均為正整數(shù)），記第 j個節(jié)點(diǎn)的分?jǐn)?shù)為 di， tree及它的每個子樹都有一個加分，任一棵子樹 subtree（也包含 tree本身）的加分計算方法如下： 例 6. 加分二叉樹（ NOIP2022） ? subtree的左子樹的加分 subtree的右子樹的加分
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1