動態(tài)規(guī)劃專題

MT2149 最長子段和

難度：鉆石 ?? 時(shí)間限制：1秒 ?? 占用內(nèi)存：128M

題目描述

給出一個(gè)長度為 $n$ 的序列 $A$，選出其中連續(xù)且非空的一段使得這段和最大。

格式

輸入格式：第一行是一個(gè)整數(shù)，表示序列的長度 $n$；
?????第二行有 $n$ 個(gè)整數(shù)，第 $i$ 個(gè)整數(shù)表示序列的第 $i$ 個(gè)數(shù)字 $a_i$。
輸出格式：輸出一行一個(gè)整數(shù)表示答案。

樣例 1

輸入：7
???2 -4 3 -1 2 -4 3

輸出：4

備注

其中： $1\le n\le 2e5,?1e4\le a_i\le 1e4$。

相關(guān)知識點(diǎn)：動態(tài)規(guī)劃

題解

若設(shè)轉(zhuǎn)移數(shù)組 dp[i] 表示 “以序號i結(jié)尾的子數(shù)列中的最大連續(xù)子段和”，則對輸入的整個(gè)序列（ary[ ]）而言，每個(gè) dp[i] 的最低取值即為 ary[i]。此時(shí)，每個(gè)子序列都取第 $i$ 個(gè)元素構(gòu)成單元素序列。在這樣的定義下，最終我們要求的就是 $ma{x}_{i\in [1,n]}d[i]$。

接下來討論此模型的動態(tài)轉(zhuǎn)移方程。由于我們每次更新 dp[i] 時(shí)，dp[i-1]都 已經(jīng)存儲好了 “以 $i?1$ 結(jié)尾的最大連續(xù)子段和”，因此，dp[i] 要想取得 “以 $i$ 結(jié)尾的子數(shù)列中的最大連續(xù)子段和” 就只需加上 dp[i-1] 即可。但是，加上的 dp[i-1] 必須大于0，否則這樣的 “加上” 實(shí)際上會成為 “減少”。所以該模型的動態(tài)轉(zhuǎn)移方程即為（其中，ary[ ]為原序列數(shù)組，i 為循環(huán)遍歷指針）：

if(dp[i-1] >= 0)
	dp[i] = ary[i]+dp[i-1];

注：在實(shí)際編碼時(shí)，為節(jié)約內(nèi)存可直接令 dp[ ]=ary[ ]，則此時(shí)轉(zhuǎn)移方程為：dp[i] = dp[i]+dp[i-1]。
接下來只需要遍歷 dp[ ] 數(shù)組并取出其中的最大值即可。

根據(jù)這樣的思路可寫出以下代碼（已 AC）：

/*
    MT2149 最長子段和 
*/ 

#include<bits/stdc++.h> 
using namespace std;

const int MAX = 2e5+5;
int dp[MAX];

int main( )
{
    // 錄入數(shù)據(jù) 
    int n;cin>>n;
    for(int i=0;i<n;i++)
        cin>>dp[i];
    
    // 初始化結(jié)果 
    int ans = dp[0];
    
    // 狀態(tài)轉(zhuǎn)移
    for(int i=1;i<n;i++){
        if(dp[i-1] >= 0)
            dp[i] += dp[i-1];
        ans = max(ans, dp[i]);
    }
    
    // 輸出結(jié)果
    cout<<ans<<endl; 
    
    return 0;
}

注：這道題的解法實(shí)際上非常多，還有更節(jié)約存儲空間的求解方式：? 傳送門

MT2150 旅費(fèi)

難度：黃金 ?? 時(shí)間限制：1秒 ?? 占用內(nèi)存：128M

題目描述

提瓦特大陸上有個(gè)貧窮的占星術(shù)士小碼哥，他要從蒙德去往璃月，兩個(gè)地方相隔很遠(yuǎn)，所以要搭乘車隊(duì)。但是搭乘車隊(duì)需要金幣，而小碼哥沒有太多金幣，幸運(yùn)的是，車隊(duì)在這一路上有 $n$ 個(gè)?？奎c(diǎn)，每兩個(gè)?？奎c(diǎn)之間所需要的金幣數(shù)不一樣，如果能選擇好的話說不定能省點(diǎn)錢。于是小碼哥找來了每個(gè)站點(diǎn)之間所需的路費(fèi)，請你幫他找出他完成這一旅途所需要的最少的旅費(fèi)。。

格式

輸入格式：第一行輸入一個(gè)數(shù) $n$，表示馬車中間停靠的站點(diǎn)數(shù)。
?????接下來一個(gè) $n+1$ 行的半矩陣，表示從蒙德開始，每個(gè)站點(diǎn)到接下來每個(gè)站點(diǎn)所需要的金幣數(shù)。
輸出格式：輸出一行一個(gè)整數(shù)，表示完成這一旅途所需要的最少旅費(fèi)（金幣數(shù)）。

樣例 1

輸入：1
???6 18
???9

輸出：15

備注

其中: $1\le n\le 1000$。
任意兩站間的所需旅費(fèi)不超過10000。
輸入數(shù)據(jù) 1 解釋：
6（表示從蒙德到站點(diǎn)1需花費(fèi)6金幣）、18（表示從蒙德到璃月需花費(fèi)18金幣）
9（表示從站點(diǎn)1到璃月需花費(fèi)9金幣）

相關(guān)知識點(diǎn)： 動態(tài)規(guī)劃

題解

首先對 “半矩陣” 做一個(gè)解釋。對于題目輸入的站點(diǎn)數(shù) $n$，實(shí)際上還需要算上起始站和終點(diǎn)站，也就是說共有 $n+2$ 個(gè)站。若將這 $n+2$ 個(gè)站視為節(jié)點(diǎn)，則它們之間會有 $\frac{\left(n+2\right)\left(n+1\right)}{2}$ 條邊（視為無向圖）。因此，由這些節(jié)點(diǎn)構(gòu)成的可達(dá)矩陣中，會形成 $\frac{\left(n+2\right)\left(n+1\right)}{2}$條路段。而這些路段只占據(jù)了 $\left(n+2\right)\left(n+2\right)$ 規(guī)格的矩陣的一半（近似），因此稱 “提供了 $\left(n+1\right)$ 行的半矩陣”。例如，題目給出的數(shù)據(jù)可用下圖表示：

從上圖不難看出，完成這一旅途所需要的最少的旅費(fèi)為 6+9=15。

對于題目給出的站點(diǎn)數(shù)據(jù)，我們可以將其進(jìn)行編號：如蒙德→0，站點(diǎn)1→1，璃月→2（這樣一來，對輸入的站點(diǎn)總數(shù) $n$ ，終點(diǎn)站的位置始終為 $n+1$）。對 “求最小旅費(fèi)” 的要求，可設(shè)轉(zhuǎn)移數(shù)組 dp[i] 為 “從第 $i$ 個(gè)站點(diǎn)到終點(diǎn)站的最小旅費(fèi)”。那么顯然有 dp[n+1] = 0（終點(diǎn)到終點(diǎn)的旅費(fèi)為 0），且最終待求的最小旅費(fèi)為 dp[0]。同時(shí)，可知轉(zhuǎn)移數(shù)組 dp[ ] 的更新方向是從后往前。

由于 dp[i] 表示 “從第i個(gè)站到終點(diǎn)站的最小旅費(fèi)”，則在進(jìn)行前向更新時(shí)，若想要 dp[i] 盡可能小，就只能在 “上一次計(jì)算得到的dp[ ]數(shù)組中，由站 $i$ 到終點(diǎn)站的最低費(fèi)用” 和 “當(dāng)前站直接到中轉(zhuǎn)站 $j$ 的票價(jià)+上一次計(jì)算得到的由站 $j$ 到終點(diǎn)站的最低費(fèi)用” 中選更低的票價(jià)。于是可得到此題的狀態(tài)轉(zhuǎn)移方程為：

dp[i] = min(dp[i], ary[i][j]+dp[j])

顯然，這需要枚舉所有的中轉(zhuǎn)情況，即要遍歷上面的 “半矩陣”。例如，對以下測試數(shù)據(jù)（假設(shè)半矩陣信息被存儲進(jìn)數(shù)組 ary[ ][ ] 中）：

根據(jù)以上思路可寫出求解該題的完整代碼（已 AC）：

首先置各 dp[i] 為 ary[i][n+1]（即，初始直接將 “第 $i$ 個(gè)站到終點(diǎn)站的最小旅費(fèi)” 設(shè)為 “第 $i$個(gè)站直接到終點(diǎn)站的票價(jià)”）。于是有：

• dp[0] = ary[0][3] = 30;
• dp[1] = ary[1][3] = 16;
• dp[2] = ary[2][3] = 9;
• dp[3] = ary[3][3] = 0;

接下來逆向更新 dp[ ] 數(shù)組：

1. i = 2（即討論站點(diǎn) 2 到終點(diǎn)的最低旅費(fèi)），當(dāng)前 dp[]={30,16,9,0}。dp[ ] 數(shù)組上一次存放的從站點(diǎn) 2 到終點(diǎn)的最低旅費(fèi) dp[2] = 9。接下來向后遍歷，取各個(gè)站作為中轉(zhuǎn)站以嘗試尋找更低的旅費(fèi)組合方案。
   ① 以 j = i+1 = 3 作為中轉(zhuǎn)站，此時(shí)的旅費(fèi)為：ary[2][3]+dp[3] = 9+0 = 9 = dp[2]，故無需更新。
   后向遍歷結(jié)束，得到從站點(diǎn) 2出發(fā)到終點(diǎn)站的最低旅費(fèi)為 9。
2. i = 1（即討論站點(diǎn) 1 到終點(diǎn)的最低旅費(fèi)），當(dāng)前 dp[]={30,16,9,0}。dp[ ] 數(shù)組上一次存放的從站點(diǎn) 1 到終點(diǎn)的最低旅費(fèi) dp[1] = 16。接下來向后遍歷，取各個(gè)站作為中轉(zhuǎn)站以嘗試尋找更低的旅費(fèi)組合方案。
   ① 以 j = i+1 = 2 作為中轉(zhuǎn)站，此時(shí)的旅費(fèi)為：ary[1][2]+dp[2] = 8+9 = 17 > dp[1]，故無需更新；
   ② 以 j = i+2 = 3 作為中轉(zhuǎn)站，此時(shí)的旅費(fèi)為：ary[1][3]+dp[3] = 16+0 = 16 = dp[1]，故無需更新。
   后向遍歷結(jié)束，得到從站點(diǎn) 1 出發(fā)到終點(diǎn)站的最低旅費(fèi)為 16。
3. i = 0（即討論從起點(diǎn)到終點(diǎn)的最低旅費(fèi)），當(dāng)前 dp[]={30,16,9,0}。dp[ ] 數(shù)組上一次存放的從站點(diǎn) 0 到終點(diǎn)的最低旅費(fèi) dp[0] = 30。接下來向后遍歷，取各個(gè)站作為中轉(zhuǎn)站以嘗試尋找更低的旅費(fèi)組合方案。
   ① 以 j = i+1 = 1 作為中轉(zhuǎn)站，此時(shí)的旅費(fèi)為：ary[0][1]+dp[1] = 6+16 = 22 < dp[1]，故更新 dp[1] = 22；
   ② 以 j = i+2 = 2 作為中轉(zhuǎn)站，此時(shí)的旅費(fèi)為：ary[0][2]+dp[2] = 15+9 = 24 > dp[1]，故無需更新；
   ③ 以 j = i+3 = 3 作為中轉(zhuǎn)站，此時(shí)的旅費(fèi)為：ary[0][3]+dp[3] = 30+0 = 30 > dp[1]，故無需更新。
   后向遍歷結(jié)束，得到從站點(diǎn) 0（起點(diǎn)）出發(fā)到終點(diǎn)站的最低旅費(fèi)為 22。
   算法終止，最終得到 dp[ ] 數(shù)組內(nèi)容為：dp[ ]={22,16,9,0}。

此外，注意到每次對某個(gè)站點(diǎn)的 dp[ ] 數(shù)組進(jìn)行更新時(shí)，由于一開始初始化已經(jīng)將 “第 $i$ 個(gè)站到終點(diǎn)站的最小旅費(fèi)” 設(shè)為 “第 $i$ 個(gè)站直接到終點(diǎn)站的票價(jià)”，所以在后續(xù)更新時(shí)就沒必要再判斷 “以終點(diǎn)站為中轉(zhuǎn)站” 時(shí)的情況，因?yàn)樗跏既≈稻褪侵边_(dá)終點(diǎn)的票價(jià)。

故此，可寫出求解此題的完整代碼（已 AC）：

/*
    MT2150 旅費(fèi)
*/

#include<bits/stdc++.h> 
using namespace std;

const int MAX = 1e3+5;
int ary[MAX][MAX], dp[MAX];

int main( )
{
    // 錄入數(shù)據(jù) 
    int n;cin>>n;
    n++;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<=n;j++)
            cin>>ary[i][j];
        // 初始化 dp[] 數(shù)組
        dp[i] = ary[i][n];
    }
    
    // 狀態(tài)轉(zhuǎn)移
    for(int i=n-1;i>=0;i--)
        for(int j=i+1;j<=n;j++)
            dp[i] = min(dp[i], ary[i][j]+dp[j]);
    
    // 輸出結(jié)果
    cout<<dp[0]<<endl; 
    
    return 0;
}

MT2156 矩陣取數(shù)

難度：鉆石 ?? 時(shí)間限制：1秒 ?? 占用內(nèi)存：128M

題目描述

給定 $n\times m$ 的整數(shù)矩陣 $A$，要求每行只能選取不超過一半的元素，且總的選擇元素的和要是 $k$ 的倍數(shù)，求滿足條件的和的最大值

格式

輸入格式：第一行為 $n,m,k$；
?????接下來 $n$ 行，為所描述的矩陣
輸出格式：輸出一個(gè)整數(shù)為所求答案。

樣例1

輸入：3 4 3
???1 2 3 4
???5 2 2 2
???7 1 1 4

輸出：24

備注

所有數(shù)據(jù)均在 70 以內(nèi)，且大于0。

相關(guān)知識點(diǎn)：動態(tài)規(guī)劃

題解

這道題其實(shí)和背包問題非常相似，不過這道題的難度稍大點(diǎn)，因?yàn)樗木S度為 2。

為便于理解這道題，下面先說明對一維情況的求解。即，現(xiàn)在有數(shù)組 a r y = { a 1 , a 2 , … , a m } ary=\left\{a_1,a_2,\ldots,a_m\right\} ary={a1?,a2?,…,am?} ，要求你在其中選不超過一半的數(shù)使得這些數(shù)的總和是 $k$ 的倍數(shù)，且盡可能大。
待求問題的解涉及到兩個(gè)參數(shù)：選了哪些數(shù)？總和對 $k$ 的模？即，這兩個(gè)參數(shù)的變動會對解或狀態(tài)轉(zhuǎn)移造成影響。但對第一個(gè)參數(shù)而言，我們更需要關(guān)注的是它選了多少個(gè)數(shù)（因?yàn)橹懒诵蛄械目傞L度后，可以通過循環(huán)遍歷來找到最優(yōu)組合，此處的最優(yōu)當(dāng)然是指在對 $k$ 求模后得到的和盡可能大）。因此，可以設(shè)狀態(tài)數(shù)組 dp[l][r] 表示 “當(dāng)前從序列中選了 $l$ 個(gè)數(shù)，$l$ 個(gè)數(shù)的總和是 dp[l][r]，dp[l][r] 對 $k$ 的模為 $r$”。基于這樣的設(shè)置，接下來可通過一層循環(huán)來遍歷整個(gè)數(shù)組 $ary$ ，并在該循環(huán)內(nèi)部再通過一層循環(huán)（保證所選數(shù)的個(gè)數(shù)不超過原數(shù)組元素的半數(shù)），不斷嘗試 “不同數(shù)量下的各種數(shù)字組合”，并將總和更大的組合方式保存下來。當(dāng)整個(gè)循環(huán)結(jié)束時(shí)，dp[][] 數(shù)組的最后一行中存放的就是各種取數(shù)情況下（取數(shù)總和對 $k$ 的余數(shù)）能夠拿到的最大總和。即，狀態(tài)轉(zhuǎn)移過程為：

for(int i=1; i<m; i++)
	for(int l=m/2-1; l>=0; l++)
		for(int r=0; r<k; r++)
			dp[l+1][(r+ary[i])%k] = max(dp[l+1][(r+ary[i])%k], dp[l][r]+ary[i])

有一個(gè)細(xì)節(jié)：為什么狀態(tài)轉(zhuǎn)移過程中，第二重循環(huán)要從 $\frac{m}{2}?1$開始往前遍歷呢？這其實(shí)和背包問題的要求有關(guān)。如果題目給出的對象（也就是本題中的數(shù)組元素）要求不能被重復(fù)選擇，則必須逆向遍歷；如果可多次選擇，則需要正向遍歷（對這個(gè)問題感興趣的可以看這篇文章 ? 傳送門）。

對于本題而言，稍微復(fù)雜的點(diǎn)在于，現(xiàn)在要從一個(gè)矩陣 a r y n × m = { a 1 , 1 , a 1 , 2 , … , a 1 , m , ? … , a n , 1 , a n , 2 , … , a n , m } ary_{n\times m}=\left\{a_{1,1},a_{1,2},\ldots,a_{1,m},\ \ldots,a_{n,1},a_{n,2},\ldots,a_{n,m}\right\} aryn×m?={a1,1?,a1,2?,…,a1,m?,?…,an,1?,an,2?,…,an,m?} 中選數(shù)，且對矩陣的每一行選數(shù)不能超過其列數(shù)的一半。首先，同樣需要分析會影響狀態(tài)轉(zhuǎn)移過程的參數(shù)，很明顯，依然是“選了哪些數(shù)”以及“總和對 $k$ 的?！薄５?，由于現(xiàn)在處理的數(shù)據(jù)對象是一個(gè)二維矩陣，因此在 “選了哪些數(shù)” 這個(gè)問題上，它需要兩個(gè)參數(shù)：一個(gè)說明當(dāng)前選了多少行，另一個(gè)說明在當(dāng)前行選了多少的數(shù)。因此，可以設(shè)狀態(tài)數(shù)組 dp[i][l][r] 表示 “當(dāng)前已經(jīng)遍歷到第 $i$ 行（說明前面 $i?1$ 行已經(jīng)完成了最優(yōu)組合的尋找，實(shí)際上可以視該過程為記憶化搜索），并且在此行選了l個(gè)數(shù)，目前所選數(shù)的總和為 dp[i][j][r]，其對 $k$ 的模為 $r$”。基于這種設(shè)置，接下來可通過一個(gè)二重循環(huán)來遍歷矩陣 $ar{y}_{n\times m}$，并在其內(nèi)部采用和一維情況相似的思路進(jìn)行狀態(tài)轉(zhuǎn)移。但是有一個(gè)不同的地方在于，狀態(tài)轉(zhuǎn)移過程是針對某一行的數(shù)據(jù)進(jìn)行的，它的目的是求出當(dāng)前這一行最優(yōu)的選數(shù)組合（使得所選數(shù)對 $k$ 的模在指定前提下還具有最大總和）。因此。在進(jìn)行二維狀態(tài)轉(zhuǎn)移時(shí)，我們還需要建立每一行之間的最優(yōu)值傳遞。即，在尋找第i行的最優(yōu)取數(shù)時(shí)，需要將前面 $i?1$ 行已經(jīng)得到的結(jié)果傳遞過來。為此，需要在狀態(tài)轉(zhuǎn)移過程中的每一行的第一列進(jìn)行行之間的狀態(tài)轉(zhuǎn)移。下面給出二維情況下的狀態(tài)轉(zhuǎn)移過程：

for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			// 行之間的狀態(tài)轉(zhuǎn)移 
			if(j == 1){
				for(int l=0;l<=m/2;l++)
					for(int r=0; r<k; r++)
						dp[i][0][r] = max(dp[i][0][r], dp[i-1][l][r]);
			}
			// 列之間的狀態(tài)轉(zhuǎn)移 
			for(int l=m/2-1;l>=0;l--)
				for(int r=0; r<k;r++)
					dp[i][l+1][(r+ary[i][j])%k] = max(dp[i][l+1][(r+ary[i][j])%k], dp[i][l][r]+ary[i][j]);
		}

當(dāng)遍歷完整個(gè)二維矩陣后，最終的結(jié)果將存放在 dp[n][0-m/2][0] 中。
下面給出基于以上思路得到的完整代碼（已 AC）：

/*
    MT2156 矩陣取數(shù) 
*/

#include<bits/stdc++.h> 
using namespace std;

const int MAX = 75;
const int INF = 0x3f3f3f3f; 
int ary[MAX][MAX], dp[MAX][MAX][MAX];

int main( )
{
    // 錄入數(shù)據(jù) 
    int n, m, k, ans = -INF;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>ary[i][j];
    
    // 狀態(tài)數(shù)組初始化
    memset(dp, -INF, sizeof(dp));
    dp[0][0][0] = 0;
    
    // 狀態(tài)轉(zhuǎn)移
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            // 行之間的狀態(tài)轉(zhuǎn)移 
            if(j == 1){
                for(int l=0;l<=m/2;l++)
                    for(int r=0; r<k; r++)
                        dp[i][0][r] = max(dp[i][0][r], dp[i-1][l][r]);
            }
            // 列之間的狀態(tài)轉(zhuǎn)移 
            for(int l=m/2-1;l>=0;l--)
                for(int r=0; r<k;r++)
                    dp[i][l+1][(r+ary[i][j])%k] = max(dp[i][l+1][(r+ary[i][j])%k], 
                    dp[i][l][r]+ary[i][j]);
        }
    
    // 在最后一層尋找最大值
    for(int j=0;j<=m/2;j++)
        ans = max(ans, dp[n][j][0]);
    
    // 輸出結(jié)果
    cout<<ans<<endl; 
    
    return 0;
}

MT2157 迷宮

難度：黃金 ?? 時(shí)間限制：1秒 ?? 占用內(nèi)存：128M

題目描述

小碼哥和他的手下在維多利亞的迷宮玩耍，小碼哥并不喜歡這個(gè)項(xiàng)目，于是他決定以最快的速度結(jié)束這個(gè)項(xiàng)目，這個(gè)迷宮可以看作是一個(gè)直角坐標(biāo)系，小碼哥在左下，終點(diǎn)在右上點(diǎn)。
小碼哥只沿 $x,y$ 軸的正方向走，因?yàn)檫@樣是理論最快的解，問小碼哥有多少種行走方法來最快到達(dá)終點(diǎn)。

格式

輸入格式：第一行兩個(gè)整數(shù) $m,n$ 表示迷宮是 $m$ 行 $n$ 列；
?????接下來 $m$ 行，每行 $n$ 個(gè)數(shù)描述了地圖。
?????0 – 空地
?????1 – 墻（無法通過）
輸出格式：一個(gè)整數(shù)表示答案（mod 2333）。

樣例 1

輸入：3 3
???0 0 0
???0 1 0
???0 0 0

輸出：2

備注

其中： $m,n\le 3000$。

相關(guān)知識點(diǎn)：動態(tài)規(guī)劃

題解

走迷宮問題是二維動態(tài)規(guī)劃里非常經(jīng)典的一類題目。考慮到表達(dá)上的習(xí)慣，我們可以對本題的任務(wù)方向進(jìn)行一個(gè)改變：即現(xiàn)假設(shè)從二維矩陣的最左上角往最右下角走。并規(guī)定數(shù)組的索引從1開始，當(dāng)方向向下和向右走時(shí)，在對應(yīng)維度上的索引號增加：

由于處理對象是二維矩陣，因此可設(shè)狀態(tài)數(shù)組 dp[i][j] 表示 “走到位置 $\left(i,j\right)$ 時(shí)共有 dp[i][j] 種行走方式”，則最終待求的就是 dp[m][n]。對任意位置 $\left(i,j\right)$ 而言，只能由其左方 $\left(i,j?1\right)$ 或上方 $\left(i?1,j\right)$ 的位置而來。也就是說，dp[i][j] 的前一個(gè)狀態(tài)只能是 dp[i][j-1] 或 dp[i-1][j]。因此，可得到本題的狀態(tài)轉(zhuǎn)移方程為：

dp[i][j] = dp[i][j] + (dp[i-1][j]+dp[i][j-1])

下面給出求解該題的完整代碼（已 AC）：

/*
    MT2157 迷宮
*/

#include<bits/stdc++.h> 
using namespace std;

const int MAX = 3005;
const int MOD = 2333; 
bool ary[MAX][MAX];
int dp[MAX][MAX];

int main( )
{
    // 錄入數(shù)據(jù) 
    int n, m;
    cin>>m>>n;
    for(int i=m;i>=1;i--)
        for(int j=1;j<=n;j++)
            cin>>ary[i][j];
    
    // 狀態(tài)數(shù)組初始化
    dp[1][1] = 1; 
    
    // 狀態(tài)轉(zhuǎn)移
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            if(!ary[i][j]){
                dp[i][j] += (dp[i-1][j]+dp[i][j-1]);
                dp[i][j] %= MOD;
            }
    
    // 輸出結(jié)果
    cout<<dp[m][n]<<endl; 
    
    return 0;
}

MT2155 四柱河內(nèi)塔

難度：黃金 ?? 時(shí)間限制：1秒 ?? 占用內(nèi)存：128M

題目描述

漢諾塔問題：有三個(gè)柱子，編號為 1，2，3；在編號為 1 的柱子上有 n 個(gè)大小不同圓盤，圓盤從小到大，從上到下堆疊，你只可以移動一個(gè)柱子上最上面的圓盤。
現(xiàn)在你需要將編號為 1 的柱子上的圓盤移到 3 柱子上，順序不變；
注意：在移動過程中，不可以將大的圓盤放在小圓盤上，你一次只可以移動一個(gè)盤子；
現(xiàn)在有一個(gè) 4 個(gè)柱子的河內(nèi)塔，在規(guī)則不變的情況下，問最少需要移動多少次才能把盤子從 1 號柱子移到 4 號柱子上。

格式

輸入格式：一個(gè)整數(shù) $f$ ，表示 $n$ 取 $\left[1,f\right]$ 時(shí)的 $f$ 種情況；
輸出格式：輸出 $f$ 行，表示當(dāng) $n$ 分別取 $\left[1,f\right]$ 的情況下，需要的最少移動次數(shù)。

樣例 1

輸入：12

輸出：1
???3
???5
???9
???13
???17
???25
???33
???41
???49
???65
???81

備注

其中：$1\le n\le 50$。

相關(guān)知識點(diǎn)：動態(tài)規(guī)劃

題解

我們首先來思考，經(jīng)典漢諾塔問題（存在 A、B、C ，3 根柱子）的動態(tài)規(guī)劃解法。
假設(shè)現(xiàn)在要將 $n$ 個(gè)圓盤從 A 柱移動至 C 柱。顯然，需要的移動次數(shù)僅僅和當(dāng)前的圓盤數(shù)量 $n$ 有關(guān)。故可以假設(shè) $dp[n]$ 表示 “移動 $n$ 個(gè)圓盤到另一個(gè)柱子需要的最少移動次數(shù)”。那么將第 $n$ 個(gè)圓盤從 A 柱移動至 C 柱需要以下三步：

1. 將第 $n$ 個(gè)圓盤上的 $n?1$ 個(gè)圓盤從 A 移動至 B 柱，這一步最少需要 $dp[n?1]$ 次移動；
2. 將第 $n$ 個(gè)圓盤從 A 移動至 C 柱，這一步最少需要 1 次移動；
3. 將B柱上的 $n?1$ 個(gè)圓盤移動至 C 柱，這一步最少需要 $dp[n?1]$ 次移動。

顯然，從上面可以得到 “將 $n$ 個(gè)圓盤從 A 柱移動至 C 柱” 需要的最小移動次數(shù)為 $dp[n?1]+1+dp[n?1]=2dp[n?1]+1$。即得了經(jīng)典漢諾塔問題的狀態(tài)轉(zhuǎn)移方程為：$dp[n]=2dp[n?1]+1$。從這個(gè)公式不難看出，漢諾塔問題的最小移動次數(shù)與其圓盤總數(shù)存在以下關(guān)系：

$$dp\left[n\right]=2^n?1$$

現(xiàn)在假設(shè)存在 4 根柱子，其余要求都不變，問不同數(shù)量圓盤對應(yīng)的最少移動次數(shù)。
在只有 3 根柱子時(shí)，為了將第 $n$ 個(gè)圓盤移動至目標(biāo)柱子（C 柱），就必須將第 $n$ 個(gè)圓盤前的 $n?1$ 個(gè)圓盤均移至除所在柱子（A 柱）和目的柱子以外的第 3 根柱子（B 柱）。因此這個(gè)狀態(tài)轉(zhuǎn)移過程是唯一的。而當(dāng)柱子數(shù)多了 1 個(gè)后，這個(gè)過程變得不再唯一。因?yàn)槲覀兛梢詫⒁苿舆^程進(jìn)行分解，從而大幅降低總的移動次數(shù)。例如，對于含有 $n$ 個(gè)圓盤的柱子 A，我們可以通過以下步驟將其全部移至柱子 D：

1. 將柱子 A 上的前 $n?k$ 個(gè)圓盤先移至柱子 B，這一步最少需要 $dp[n?k]$ 次移動；
2. 將柱子 A 上剩下的 $k$ 個(gè)圓盤通過柱子 C 再移動至柱子 D；
3. 將柱子 B 上的前 $n?k$ 個(gè)圓盤移動至柱子 D，這一步最少需要 $dp[n?k]$ 次移動。

對于步驟 2，該過程實(shí)際上就是 “求具有 $k$ 個(gè)圓盤的經(jīng)典漢諾塔問題”。因?yàn)檫@一步執(zhí)行時(shí)，剩下的 $k$ 個(gè)圓盤都比柱子 B 上的更大，因此它們的移動過程只能用剩余 3 根柱子，即 A，C，D柱。

為什么分解后會大幅降低總的移動次數(shù)？從數(shù)學(xué)的角度看：因?yàn)?$f(x)=2^x$ 是一個(gè)二階導(dǎo)大于 0 的凸函數(shù)，它始終滿足 $f\left(a+b\right)\ge f\left(a\right)+f\left(b\right)$ 。因此，可通過枚舉所有的 $a+b$ 來尋找這里面具有最小取值的 $f\left(a\right)+f\left(b\right)$。例如，$f(5)=2^5=32$ ，而 $f(2)+f(3)=2^2+2^3=4+8=12$ ，可見，分解后確實(shí)能更大程度的降低需要移動的次數(shù)。

因此，如果假設(shè)四柱漢諾塔問題的狀態(tài)數(shù)組為 $DP[]$，三柱漢諾塔問題的狀態(tài)數(shù)組為 $dp[]$，則從前面的步驟可總結(jié)出四柱漢諾塔問題的狀態(tài)轉(zhuǎn)移方程為：

for(int j=1; j<n; j++)
DP[j] = 2DP[n-j]+dp[j];

下面給出基于以上思路的完整代碼（已 AC）：文章來源地址http://www.zghlxwxcb.cn/news/detail-674870.html

/*
    MT2155 四柱河內(nèi)塔
*/

#include<bits/stdc++.h> 
using namespace std;

const int MAX = 55;
const int INF = 0x3f3f3f3f; 
int dp[MAX];

int main( )
{
    int f, tmp; cin>>f;
    
    // 狀態(tài)數(shù)組初始化
    memset(dp, INF, sizeof(dp));
    dp[0] = 0, dp[1] = 1, dp[2] = 3 ;
    
    if(f>=1) cout<<1<<endl;
    if(f>=2) cout<<3<<endl;
    
    // 狀態(tài)轉(zhuǎn)移并輸出結(jié)果 
    for(int i=3;i<=f;i++){
        for(int j=1;j<i;j++){
            if(dp[i] > 2*dp[i-j] + pow(2,j) - 1)
                dp[i] = 2*dp[i-j] + pow(2,j) - 1;
        }
        // 輸出結(jié)果
        cout<<dp[i]<<endl; 
    }
    
    return 0;
}

END

到了這里，關(guān)于【馬蹄集】第十六周——動態(tài)規(guī)劃專題的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！