動(dòng)態(tài)規(guī)劃及其應(yīng)用-資料下載頁(yè)
2025-08-05 03:45本頁(yè)面
【正文】 l ef t s o nifkjif)139。,.()39。,.(),()()39。,.()39。,.(),(狀態(tài)壓縮動(dòng)態(tài)規(guī)劃 ? 有一些問(wèn)題卻被認(rèn)為很可能不存在有效的(多項(xiàng)式級(jí)的 )算法，這里以對(duì)幾個(gè)例題的剖析，簡(jiǎn)述狀態(tài)壓縮思想及其應(yīng)用。 預(yù)備知識(shí) 名稱 C/C++樣式 Pascal樣式 簡(jiǎn)記法則 按位與 amp。 and 全一則一，否則為零 按位或 | or 有一則一，否則為零 按位取反 ~ not 是零則一，是一則零 按位異或 ^ xor 不同則一，相同則零 左移位 shl ak等價(jià)于 a*2k 右移位 shr ak等價(jià)于 a/2k 引例 ? 在 n*n(n≤20)的方格棋盤上放置 n個(gè)車 (可以攻擊所在行、列 )，求使它們不能互相攻擊的方案總數(shù)。 分析 ? 其實(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)壓縮的解法。 分析 ? 我們?nèi)匀灰恍幸恍蟹胖谩? ? 取棋子的放置情況作為狀態(tài)，某一列如果已經(jīng)放置棋子則為 1，否則為 0。這樣，一個(gè)狀態(tài)就可以用一個(gè)最多 20位的二進(jìn)制數(shù)表示。 ? 例如 n=5,第 4列已經(jīng)放置，則這個(gè)狀態(tài)可以表示為 01101(從右到左 )。設(shè) fs為達(dá)到狀態(tài) s的方案數(shù)，則可以嘗試建立 f的遞推關(guān)系。 ? ① 前兩行在第 4列放置了棋子 (不考慮順序，下同 )，第三行在第 1列放置； ? ②前兩行在第 4列放置了棋子，第三行在第 3列放置； ? ③前兩行在第 3列放置了棋子，第三行在第 4列放置。 ? 這三種情況互不相交，且只可能有這三種情況，根據(jù)加法原理， fs應(yīng)該等于這三種情況的和。 ? 根據(jù)上面的討論思路推廣之，得到引例的解決辦法： ? 其中 s的右起第 i+1位為 1 ? (其實(shí)就是在枚舉 s的二進(jìn)制表示中的 1) ? 狀態(tài)壓縮具有良好的拓展性。 ? 在 n*n(n≤20)的方格棋盤上放置 n個(gè)車，某些格子不能放，求使它們不能互相攻擊的方案總數(shù)。 ? 我們只需要在原題的程序中枚舉添加 1的位置的時(shí)候進(jìn)行判斷就行。 ? program p1。 ? const ? max=1 shl 20。 ? var n,i,t,c,j,tmp,r:longint。 ? f,a:array[0..max]of int64。 ? begin ? assign(input,39。39。)。a ? reset(input)。 ? readln(n)。 ? fillchar(f,sizeof(f),0)。 ? for i:=1 to n do //讀入及預(yù)處理 ? begin ? a[i]:=0。 ? for j:=1 to n do //如果第 i行的某位為 0,表示這位不能放置 ? begin ? read(c)。 ? a[i]:=a[i] shl 1。 ? if c=1 then ? a[i]:=a[i]+1。 ? end。 ? end。 ? f[0]:=1。 ? for i:=1 to (1 shl n)1 do ? begin ? t:=i。 r:=0。 ? while t0 do //計(jì)算狀態(tài) i中 1的個(gè)數(shù)，即可得到其為第幾行 ? begin ? inc(r)。 ? t:=t(t and t)。 ? end。 ? tmp:=i and a[r]。 ? t:=tmp。 ? while t0 do //枚舉狀態(tài) tmp二進(jìn)制表示中的 1 ? begin ? f[i]:=f[i]+f[i xor (t and t)]。 ? t:=t(t and t)。 ? end。 ? end。 ? writeln(f[(1 shl n) 1])。 ? end. ? 當(dāng)然這個(gè)問(wèn)題也可以用容斥原理解決，但這個(gè)不是今天的主題，有興趣的同學(xué)可以自己思考。 例題 ? 有 一個(gè) n*m的棋盤 (n、 m≤80,n*m≤80)要在棋盤上放 k(k≤20)個(gè)棋子，使得任意兩個(gè)棋子不相鄰 (4個(gè)方向）。求合法的方案總數(shù) ? 我們看到 n*m≤80 ? 稍微 思考我們可以發(fā)現(xiàn)： 9*9=8180，即如果 n,m都大于等于 9，將不再滿足 n*m≤80這一條件。所以，我們有 n或 m小于等于 8，而28是可以承受的 ！ ? 我們假設(shè) m≤n， n是行數(shù) m是列數(shù)，則每行的狀態(tài)可以用 m位的二進(jìn)制數(shù)表示 ? 但是本題和例 1又有不同：例 1每行每列都只能放置一個(gè)棋子，而本題卻只限制每行每列的棋子不相鄰 ? 上例中枚舉當(dāng)前行的放置方案的做法依然可行。我們用數(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)。 本題狀態(tài)的 維數(shù)需要增加，原因在于并不是每一行只放一個(gè)棋子，也不是每一行都要求有棋子，原先的表示方法已經(jīng)無(wú)法完整表達(dá)一個(gè)狀態(tài)。 ? 我們用 fi,j,k表示第 i行的狀態(tài)為 sj且前 i行 總共 放置 k個(gè)棋子 （ 下 面 用 pn代替原題中的 k） 的方案數(shù)。沿用枚舉當(dāng)前行方案的做法，只要當(dāng)前行的 放置 方案和上一行的不沖突 。微觀地講，就是要兩行的狀態(tài) s1和 s2中沒(méi)有同為 1的位即可，亦即 s1 and s2=0 ? 然而，雖然我們枚舉了第 i行的放置方案，但卻不知道其上一行 (第 i1行 )的方案 ? 為了解決這個(gè)問(wèn)題，我們不得不 連第 i1行的狀態(tài)一起枚舉 ，則可以寫出遞推式： ? 其中 s1=0，即在當(dāng)前行不放置棋子； ? j和 p是需要枚舉的兩個(gè)狀態(tài)編號(hào)。 例題 ? 給出一個(gè) n*m(n≤100,m≤10)的棋盤，一些格子不能放置棋子。求最多能在棋盤上放置多少個(gè)棋子，使得每一行每一列的任兩個(gè)棋子間至少有兩個(gè)空格。 –題目來(lái)源： NOI2022《 炮兵陣地 》 ? 仍然先用 DFS搜出一行可能狀態(tài) s， 依舊 用c數(shù)組保存 s中 1的個(gè)數(shù)，依照例 1的預(yù)處理搞定不能放置棋子的格子 （應(yīng)該有這種意識(shí)） ? 問(wèn)題是，這個(gè)題目的狀態(tài)怎么選？繼續(xù)像例 2那樣似乎不行，原因在于棋子的攻擊范圍加大了 ? 但是我們照葫蘆畫瓢：例 2的攻擊范圍只有一格，所以我們的狀態(tài)中只需要有當(dāng)前行的狀態(tài) ，再枚舉上一行的狀態(tài) 即可進(jìn)行遞推 ； 而本題攻擊范圍是兩格，因此增加一維來(lái)表示上一行的狀態(tài) 。 ? 用 fi,j,k表示第 i行狀態(tài)為 sj、第 i1行狀態(tài)為 sk時(shí)前 i行至多能放置的棋子數(shù) 。 則狀態(tài)轉(zhuǎn)移方程很容易寫出 ： ? 同時(shí)我們可以用滾動(dòng)數(shù)組優(yōu)化空間。
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1