動態(tài)規(guī)劃及其應用(已改無錯字)
2022-09-02 03:45:54 本頁面
【正文】 ls:=f[tree[t].lc,i]。//記錄左子樹的值 ? rs:=f[tree[t].rc,ki1]。//記錄右子樹的值 ? if f[t,k]ls+rs then f[t,k]:=ls+rs。//比較 ? end。 ? f[t,k]:=f[t,k]+tree[t].s。 //保存最優(yōu)值 ? end。 例題 ? [問題描述 ] ? 在大學里每個學生，為了達到一定的學分，必須從很多課程里選擇一些課程來學習，在課程里有些課程必須在某些課程之前學習，如高等數(shù)學總是在其它課程之前學習?，F(xiàn)在有 N門功課，每門課有個學分，每門課有一門或沒有直接先修課（若課程 a是課程 b的先修課即只有學完了課程a，才能學習課程 b）。一個學生要從這些課程里選擇 M門課程學習，問他能獲得的最大學分是多少？ ? 輸入： ? 第一行有兩個整數(shù) N,M用空格隔開。 (1=N=200,1=M=150) ? 接下來的 N行 ,第 I+1行包含兩個整數(shù) ki和 si, ki表示第 I門課的直接先修課，si表示第 I門課的學分。若 ki=0表示沒有直接先修課（ 1=ki=N, 1=si=20）。 ? 輸出： ? 只有一行，選 M門課程的最大得分。 輸入： 輸出： 7 4 2 2 0 1 0 4 2 1 7 1 7 6 2 2 13 樣例： 分析 ? 根據(jù)先修關(guān)系，選修的課程組成了一個森林，我們虛擬一個根節(jié)點 0作為這棵森林的總根 ? 然后我們把一棵普通樹轉(zhuǎn)化為二叉樹進行求解。 ? 讀入數(shù)據(jù)時把二叉樹建好：第一個孩子作為父節(jié)點的左子樹，其它孩子作為第一個孩子的右子樹。 ? F（ i， j）：表示節(jié)點以 i為根結(jié)點取 j門課的最高學分，則 }m a x {),( ][)1,(),( ),( iskjr i g h t cfkl e f t cf jr i g h t cfjif ?????? F(leftc,k)：表示左子樹選了 k門課的最大學分。 ? F(rightc,j)：表示右子樹選了 j門課的最大學分。 ? F[leftc,k]+f[rightc,jk1]+s[i]：表示左子樹選了 k門，當然選了左子樹，必須選根，右子樹選了 jk1門。 ? 其實是四種情況決策： (1) 選右子樹中 j門（ 2）選左子樹（ j1）門 +根 （ 3）選右子樹（ j1門） +根 （ 4）選左子樹（ k門） +根 +選右子樹（ jk1） ? 程序中節(jié)點－ 1表示空節(jié)點， 0是根節(jié)點， 1— n是n門可選課程的節(jié)點 . ? 源程序代碼： ? program bluewater。 ? type ? tree=record ? l,r,k:longint。 ? end。 ? var ? s:string。 ? i,j,k,l:longint。 ? n,m:longint。 ? a:array[0..200] of tree。//存儲樹的信息 ? b:array[1..200,0..150] of integer。//狀態(tài)表示 ? f:array[0..200] of longint。//存父親節(jié)點 ? procedure treedp(x,y:longint)。 ? var i,j,k,l:longint。 ? begin ? if b[x,y]=0 then exit。 ? treedp(a[x].r,y)。{只有右子樹的情況 } ? j:=b[a[x].r,y]。 ? for k:=1 to y do{左右子樹都有的情況 } ? begin ? treedp(a[x].l,k1)。 ? treedp(a[x].r,yk)。 ? i:=b[a[x].l,k1]+b[a[x].r,yk]+a[x].k。 ? if ij then j:=i。 ? end。 ? b[x,y]:=j。 ? end。 ? begin ? readln(s)。 ? assign(input,s)。reset(input)。 ? readln(n,m)。 ? fillchar(f,sizeof(f),0)。 ? for i:=0 to n do ? begin a[i].l:=1。a[i].r:=1。a[i].k:=1。end。 ? {建樹 } ? for i:=1 to n do ? begin ? readln(k,l)。 ? a[i].k:=l。 ? if f[k]=0 then a[k].l:=i ? else a[f[k]].r:=i。 ? f[k]:=i。 ? end。 ? {邊界 } ? for i:=1 to n do ? for j:=1 to m do ? if (i=1) or (j=0) then b[i,j]:=0 else b[i,j]:=1。 ? {記憶化實現(xiàn)動規(guī) } ? treedp(a[0].l,m)。 ? {輸出 } ? writeln(b[a[0].l,m])。 ? end. ? 時間復雜度最大為 O(n^3) ? 思考 :若本題加上選那些課程可得到這個最大學分 ,怎樣修改程序？ ? 河流 (IOI2022) ? 一顆有 N+1個結(jié)點的樹，樹中的每個結(jié)點可能會生產(chǎn)出一些產(chǎn)品。這些產(chǎn)品要么就地加工（要有加工廠才行），要么運送到它的父親結(jié)點那兒去。現(xiàn)在在整棵樹的根結(jié)點處已經(jīng)有了一個產(chǎn)品加工廠，而且所有的產(chǎn)品最終必須在某個加工廠加工才行。由于運費昂貴，不可能將所有的產(chǎn)品都運送到根節(jié)點處加工?，F(xiàn)在決定在樹中的某些結(jié)點新增總共 K個加工廠，現(xiàn)在要你選擇這K個加工廠的廠址。 ? 假設結(jié)點 i會生產(chǎn)出 Wi噸產(chǎn)品，它的父結(jié)點是 Pi。而它到它的父結(jié)點的路徑的長度是 Ui。運費的計算是每運送 1頓的貨物，每單位長度收取 1的費用。根節(jié)點的編號為 0。 ? 例如下圖， 0節(jié)點是根節(jié)點，如果要新增兩個工廠，最佳方案是建在 3兩個節(jié)點上，這樣總的費用為： ? 1*1（ 1號） +1*3（ 4號） =4 ? 分析：由于題目中給出的樹是多叉樹，不便于進行動態(tài)規(guī)劃。我們先利用兒子兄弟表示法，將多叉樹轉(zhuǎn)化為二叉樹 ? 進行了相關(guān)的轉(zhuǎn)化之后，設 f(i,j,k)表示在新樹中，以 i結(jié)點為根的子樹中，分配 k個加工廠。并且離 i結(jié)點最近的加工廠在 j結(jié)點的情況下。 i結(jié)點及其子樹內(nèi)的所有產(chǎn)品，加工所需要的費用。 ? 轉(zhuǎn)移方程很容易就可以寫出來： ? ? 總時間復雜度為 O(N^2K^2)。 ?????????????處設廠處不設廠，ikkjr i g h t s o nifkil ef t s o nifijiD i siwkkjr i g h t s o nifkj
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1