noip教程動(dòng)態(tài)規(guī)劃ppt課件-文庫(kù)吧資料
2025-05-11 18:18本頁(yè)面
【正文】 子樹 subtree（也包含 tree本身）的加分計(jì)算方法如下： 例 6. 加分二叉樹（ NOIP2022） ? subtree的左子樹的加分 subtree的右子樹的加分＋ subtree的根的分?jǐn)?shù) ? 若某個(gè)子樹為主，規(guī)定其加分為 1，葉子的加分就是葉節(jié)點(diǎn)本身的分?jǐn)?shù)。小朋友一開始在某一個(gè)位置，在他左邊和右邊分別有一些燈，給出這些燈和他的距離以及每個(gè)燈每秒會(huì)造成的損失，求一個(gè)方案使得損失最小，輸出最小損失。編一程序 ,由文件讀入堆數(shù) N及每堆石子數(shù) (≤20), (1)選擇一種合并石子的方案 ,使得做 N1次合并 ,得分的總和最少 (2) 選擇一種合并石子的方案 ,使得做 N1次合并 ,得分的總和最大 例 4. 石子合并 Example 貪 心 N=5， 石子數(shù)分別為 3 4 6 5 4 2 用貪心法的合并過(guò)程如下： 第一次 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 顯然，貪心法是錯(cuò)誤的。 ? N=1000,C=10000 例 2. zbrka ? 狀 態(tài) ：F[i][j]表示 1～ i的一個(gè)排列，逆序 對(duì) 數(shù)目 為 j的方案數(shù) ? 枚 舉 1的位置 ? F[i][j]=sigma(F[i1][jk]),0=k=i1 ? 時(shí)間復(fù)雜度： O(N*N*C) ? 空間復(fù)雜度： O(N*C) ? ? Solution ? F[i][j]=F[i][j1]+F[i1][j]F[i1][ji] ? 第 i階段只與第 i1階段有關(guān) ? 滾動(dòng)數(shù)組，省掉一維 ? 時(shí)間復(fù)雜度： O(N*C) ? 空間復(fù)雜度： O(C) Solution ? 如圖，已知一個(gè)有向圖，求一條從最左邊的點(diǎn)走到最右邊點(diǎn)的方案（只能從左往右走），使得所經(jīng)過(guò)的權(quán)值和除以 4的余數(shù)最小。例如，數(shù)列（ 1， 4， 3， 2）的逆序數(shù)為 3，因?yàn)榇嬖谌齻€(gè)逆序?qū)Γ海?4， 3），（ 4， 2）和（ 3， 2）。 ? 在這個(gè)數(shù)列中從左到右任取兩個(gè)數(shù)，如果前
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1