動(dòng)態(tài)規(guī)劃及其應(yīng)用(參考版)
2024-08-16 03:45本頁(yè)面
【正文】 。 ? 用 fi,j,k表示第 i行狀態(tài)為 sj、第 i1行狀態(tài)為 sk時(shí)前 i行至多能放置的棋子數(shù) 。求最多能在棋盤(pán)上放置多少個(gè)棋子，使得每一行每一列的任兩個(gè)棋子間至少有兩個(gè)空格。微觀地講，就是要兩行的狀態(tài) s1和 s2中沒(méi)有同為 1的位即可，亦即 s1 and s2=0 ? 然而，雖然我們枚舉了第 i行的放置方案，但卻不知道其上一行 (第 i1行 )的方案 ? 為了解決這個(gè)問(wèn)題，我們不得不 連第 i1行的狀態(tài)一起枚舉 ，則可以寫(xiě)出遞推式： ? 其中 s1=0，即在當(dāng)前行不放置棋子； ? j和 p是需要枚舉的兩個(gè)狀態(tài)編號(hào)。 ? 我們用 fi,j,k表示第 i行的狀態(tài)為 sj且前 i行 總共 放置 k個(gè)棋子 （ 下 面 用 pn代替原題中的 k） 的方案數(shù)。我們用數(shù)組 s保存一行中所有的 num個(gè)放置方案，則 s數(shù)組可以在預(yù)處理過(guò)程中用 DFS求出，同時(shí)用ci保存第 i個(gè)狀態(tài)中 1的個(gè)數(shù)以避免重復(fù)計(jì)算 ? 開(kāi)始設(shè)計(jì)狀態(tài)。求合法的方案總數(shù) ? 我們看到 n*m≤80 ? 稍微 思考我們可以發(fā)現(xiàn)： 9*9=8180，即如果 n,m都大于等于 9，將不再滿足 n*m≤80這一條件。 ? end. ? 當(dāng)然這個(gè)問(wèn)題也可以用容斥原理解決，但這個(gè)不是今天的主題，有興趣的同學(xué)可以自己思考。 ? end。 ? t:=t(t and t)。 ? t:=tmp。 ? end。 ? while t0 do //計(jì)算狀態(tài) i中 1的個(gè)數(shù)，即可得到其為第幾行 ? begin ? inc(r)。 ? for i:=1 to (1 shl n)1 do ? begin ? t:=i。 ? end。 ? if c=1 then ? a[i]:=a[i]+1。 ? for j:=1 to n do //如果第 i行的某位為 0,表示這位不能放置 ? begin ? read(c)。 ? fillchar(f,sizeof(f),0)。a ? reset(input)。39。 ? f,a:array[0..max]of int64。 ? const ? max=1 shl 20。 ? 我們只需要在原題的程序中枚舉添加 1的位置的時(shí)候進(jìn)行判斷就行。 ? 根據(jù)上面的討論思路推廣之，得到引例的解決辦法： ? 其中 s的右起第 i+1位為 1 ? (其實(shí)就是在枚舉 s的二進(jìn)制表示中的 1) ? 狀態(tài)壓縮具有良好的拓展性。 ? ① 前兩行在第 4列放置了棋子 (不考慮順序，下同 )，第三行在第 1列放置； ? ②前兩行在第 4列放置了棋子，第三行在第 3列放置； ? ③前兩行在第 3列放置了棋子，第三行在第 4列放置。 ? 例如 n=5,第 4列已經(jīng)放置，則這個(gè)狀態(tài)可以表示為 01101(從右到左 )。 ? 取棋子的放置情況作為狀態(tài)，某一列如果已經(jīng)放置棋子則為 1，否則為 0。 分析 ? 其實(shí)本題是一個(gè)簡(jiǎn)單的組合數(shù)學(xué)問(wèn)題，因?yàn)槊啃杏星覂H有一個(gè)車，所以我們只要來(lái)考慮每行上列的問(wèn)題，顯然每列只能出現(xiàn)一次，這題答案就是 n的一個(gè)全排列，為 ? P(n,n)=n! ? 當(dāng)然這題還有狀態(tài)壓縮的解法。 預(yù)備知識(shí) 名稱 C/C++樣式 Pascal樣式 簡(jiǎn)記法則 按位與 amp。,.()39。,.()39。 ? 轉(zhuǎn)移方程很容易就可以寫(xiě)出來(lái)： ? ? 總時(shí)間復(fù)雜度為 O(N^2K^2)。并且離 i結(jié)點(diǎn)最近的加工廠在 j結(jié)點(diǎn)的情況下。 ? 例如下圖， 0節(jié)點(diǎn)是根節(jié)點(diǎn)，如果要新增兩個(gè)工廠，最佳方案是建在 3兩個(gè)節(jié)點(diǎn)上，這樣總的費(fèi)用為： ? 1*1（ 1號(hào)） +1*3（ 4號(hào)） =4 ? 分析：由于題目中給出的樹(shù)是多叉樹(shù)，不便于進(jìn)行動(dòng)態(tài)規(guī)劃。運(yùn)費(fèi)的計(jì)算是每運(yùn)送 1頓的貨物，每單位長(zhǎng)度收取 1的費(fèi)用。 ? 假設(shè)結(jié)點(diǎn) i會(huì)生產(chǎn)出 Wi噸產(chǎn)品，它的父結(jié)點(diǎn)是 Pi。由于運(yùn)費(fèi)昂貴，不可能將所有的產(chǎn)品都運(yùn)送到根節(jié)點(diǎn)處加工。這些產(chǎn)品要么就地加工（要有加工廠才行），要么運(yùn)送到它的父親結(jié)點(diǎn)那兒去。 ? {輸出 } ? writeln(b[a[0].l,m])。 ? {邊界 } ? 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。 ? f[k]:=i。 ? a[i].k:=l。end。a[i].r:=1。 ? fillchar(f,sizeof(f),0)。reset(input)。 ? begin ? readln(s)。 ? b[x,y]:=j。 ? if ij then j:=i。 ? treedp(a[x].r,yk)。{只有右子樹(shù)的情況 } ? j:=b[a[x].r,y]。 ? begin ? if b[x,y]=0 then exit。//存父親節(jié)點(diǎn) ? procedure treedp(x,y:longint)。//存儲(chǔ)樹(shù)的信息 ? b:array[1..200,0..150] of integer。 ? n,m:longint。 ? var ? s:string。 ? type ? tree=record ? l,r,k:longint。 ? F[leftc,k]+f[rightc,jk1]+s[i]：表示左子樹(shù)選了 k門(mén)，當(dāng)然選了左子樹(shù)，必須選根，右子樹(shù)選了 jk1門(mén)。 ? F（ i， j）：表示節(jié)點(diǎn)以 i為根結(jié)點(diǎn)取 j門(mén)課的最高學(xué)分，則 }m a x {),( ][)1,(),( ),( iskjr i g h t cfkl e f t cf jr i g h t cfjif ?????? F(leftc,k)：表示左子樹(shù)選了 k門(mén)課的最大學(xué)分。 輸入： 輸出： 7 4 2 2 0 1 0 4 2 1 7 1 7 6 2 2 13 樣例： 分析 ? 根據(jù)先修關(guān)系，選修的課程組成了一個(gè)森林，我們虛擬一個(gè)根節(jié)點(diǎn) 0作為這棵森林的總根 ? 然后我們把一棵普通樹(shù)轉(zhuǎn)化為二叉樹(shù)進(jìn)行求解。若 ki=0表示沒(méi)有直接先修課（ 1=ki=N, 1=si=20）。一個(gè)學(xué)生要從這些課程里選擇 M門(mén)課程學(xué)習(xí)，問(wèn)他能獲得的最大學(xué)分是多少？ ? 輸入： ? 第一行有兩個(gè)整數(shù) N,M用空格隔開(kāi)。 例題 ? [問(wèn)題描述 ] ? 在大學(xué)里每個(gè)學(xué)生，為了達(dá)到一定的學(xué)分，必須從很多課程里選擇一些課程來(lái)學(xué)習(xí)，在課程里有些課程必須在某些課程之前學(xué)習(xí)，如高等數(shù)學(xué)總是在其它課程之前學(xué)習(xí)。 ? f[t,k]:=f[t,k]+tree[t].s。//記錄右子樹(shù)的值 ? if f[t,k]ls+rs then f[t,k]:=ls+rs。//右子樹(shù)
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1