碎碎念：因為這是隔壁lqy班的oj題目，為了白嫖算法題 ，我就用朋友的賬號幫他做。然后發(fā)現(xiàn)，兩個班題目難度差異挺大的，我們是比較基礎(chǔ)的題，隔壁班這個偏向于應(yīng)用，題意不好理解、思路也不是單一的動態(tài)規(guī)劃（比如第一題并不具有無后效性，第二題還要結(jié)合DFS…）總之，多刷算法題是沒錯的。

很巧的是，剛好在做題的時候一位電氣學(xué)院的老朋友來問我計院算法學(xué)習(xí)的難度如何，我就順手把作業(yè)截了幾張圖給他。我記得他高中學(xué)信息學(xué)奧賽的大佬，果不其然，他覺得這種題很基礎(chǔ)…嗯…

知識： 一般來說，能夠采用動態(tài)規(guī)劃方法求解的問題必須滿足.最優(yōu)化原理和無后效性原則
最優(yōu)化原理：子問題的局部最優(yōu)將導(dǎo)致整個問題的全局最優(yōu)，即問題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)，也就是說一個問題的最優(yōu)解只取決于其子問題的最優(yōu)解，非最優(yōu)解對問題的求解沒有影響
無后效性原則：未來發(fā)生的事情對于過去沒有影響，當(dāng)前的狀態(tài)是此前歷史的一個完整總結(jié)，此前的歷史只能通過當(dāng)前的狀態(tài)去影響過程未來的演變。

Problem A. 晴天小豬歷險記之Hill

時間限制 1000 ms
內(nèi)存限制 128 MB
題目描述
　　這一天，他來到了一座深山的山腳下，因為只有這座深山中的一位隱者才知道這種藥草的所在。但是上山的路錯綜復(fù)雜，由于小小豬的病情，晴天小豬想找一條需時最少的路到達(dá)山頂，但現(xiàn)在它一頭霧水，所以向你求助。
　　山用一個三角形表示，從山頂依次向下有1段、2段、3段等山路，每一段用一個數(shù)字T（1< =T< =100）表示，代表晴天小豬在這一段山路上需要爬的時間，每一次它都可以朝左、右、左上、右上四個方向走（注意：在任意一層的第一段也可以走到本層的最后一段或上一層的最后一段）。
　　晴天小豬從山的左下角出發(fā)，目的地為山頂，即隱者的小屋。

輸入數(shù)據(jù)
　　第一行有一個數(shù) n (2≤n≤1000)， 表示山的高度。
　　從第二行至第 n+1 行，第 i+1 行有 i 個數(shù)，每個數(shù)表示晴天小豬在這一段山路上需要爬的時間。
輸出數(shù)據(jù)
　　一個數(shù)，即晴天小豬所需要的最短時間。
樣例輸入
5
1
2 3
4 5 6
10 1 7 8
1 1 4 5 6
樣例輸出
10
樣例說明
在山的兩側(cè)的走法略有特殊，請自己模擬一下，開始我自己都弄錯了……

---

Problem B. 清帝之惑之順治

時間限制 1000 ms
內(nèi)存限制 128 MB
題目描述
　　順治喜歡滑雪，這并不奇怪， 因為滑雪的確很刺激。可是為了獲得速度，滑的區(qū)域必須向下傾斜，而且當(dāng)你滑到坡底，你不得不再次走上坡或者等待太監(jiān)們來載你。順治想知道載一個區(qū)域中最長的滑坡。
　　區(qū)域由一個二維數(shù)組給出。數(shù)組的每個數(shù)字代表點的高度。下面是一個例子：

1 2 3 4 5
　　16 17 18 19 6
　　15 24 25 20 7
　　14 23 22 21 8
　　13 12 11 10 9

順治可以從某個點滑向上下左右相鄰四個點之一，當(dāng)且僅當(dāng)高度減小。在上面的例子中，一條可滑行的滑坡為24-17-16-1。當(dāng)然25-24-23-…-3-2-1更長。事實上，這是最長的一條。

輸入數(shù)據(jù)
　　輸入的第一行表示區(qū)域的行數(shù) R 和列數(shù) C (1≤R,C≤500) 。下面是 R 行，每行有 C 個整數(shù)，代表高度 h,0≤h<103 。
輸出數(shù)據(jù)
　　輸出最長區(qū)域的長度。
樣例輸入
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
樣例輸出
25

分析：一開始真沒看出來和動態(tài)規(guī)劃啥關(guān)系hhh.想著用深度優(yōu)先搜索的方式暴力解出，后來一想這個規(guī)模量，天哪還是放棄吧（肯定runtime error了）。于是想到動態(tài)規(guī)劃，怎么想到的呢，這章主題就是動態(tài)規(guī)劃，所以就這樣啦。
DFS函數(shù)用來進(jìn)行深度優(yōu)先搜索，搜索到底就返回此處的最大坡度，如果某處存儲的dp!=1,說明已經(jīng)被遍歷過，根據(jù)動態(tài)規(guī)劃的原理，看作是最優(yōu)解，也就是最大坡度，然后直接return回來。
核心代碼就是:
dp[i][j]=max(dp[i][j-1],dp[i][j+1],dp[i-1][j],dp[i+1[j])+1
其中的dp[$i^{?}$][$j^{?}$]是由DFS得到的。
最后再來解答為什么可以使用動態(tài)規(guī)劃，在最前面我們提到，常規(guī)的動態(tài)規(guī)劃必然具有無后效性——后來發(fā)生的事情對于已經(jīng)確定的歷史沒有影響。事實確實是這樣。我們DFS到了某個位置的盡頭，出現(xiàn)了四面楚歌（四周都比他大）的境地，那么這個地方必然有取到最優(yōu)解1；然后遞歸上來，下一個值也可以確定最優(yōu)解：這個值的子問題的子問題的…必然也可以DFS到底，收上來就能找到答案。
深入思考還是很費腦子的。

#include<iostream> #include<cmath> using namespace std; int r, c; int a[501][501]; int dp[501][501];//dp存儲的是目前位置最高的坡度（是的，假設(shè)存儲的就是最高的，再動態(tài)地調(diào)整！) int DFS(int x, int y) {//深度優(yōu)先：找到該位置處的最大if (dp[x][y] > 1) { //如果dp有值，說明被訪問過，根據(jù)動態(tài)規(guī)劃原理，設(shè)定它為最優(yōu)值return dp[x][y];}else if (x -1 >=0 && a[x][y] > a[x - 1][y] ) {//上dp[x][y] = max(dp[x][y],DFS(x-1,y)+1); //注意：這里要加1,因為踩在小矮子的身上的}if (y >= 1 && a[x][y] > a[x][y - 1]) {//左dp[x][y] = max(dp[x][y], DFS(x, y-1)+1);}if (y+1 < c && a[x][y] > a[x][y + 1]) {//右dp[x][y] = max(dp[x][y], DFS(x, y + 1)+1);}if (x + 1 < r && a[x][y] > a[x+1][y ]) {//下dp[x][y] = max(dp[x][y], DFS(x+1, y)+1);}return dp[x][y];//這個地方，返回的就是最大值} int main() {cin >> r >> c;for (int i = 0; i < r; i++) {for (int j = 0; j < c; j++) {cin >> a[i][j];dp[i][j] = 1;//初始化為1，順治皇帝不滑站在那兒就是1}}//開始動態(tài)規(guī)劃int ans = 0;for (int i = 0; i < r; i++) {for (int j = 0; j < c; j++) {dp[i][j] =DFS(i, j);ans = max(ans,dp[i][j]);}}cout << ans; }

---

Problem C. 積木城堡

時間限制 1000 ms
內(nèi)存限制 128 MB
題目描述
XC的兒子小XC最喜歡玩的游戲用積木壘漂亮的城堡。城堡是用一些立方體的積木壘成的，城堡的每一層是一塊積木。小XC是一個比他爸爸XC還聰明的孩子，他發(fā)現(xiàn)壘城堡的時候，如果下面的積木比上面的積木大，那么城堡便不容易倒。所以他在壘城堡的時候總是遵循這樣的規(guī)則。
小XC想把自己壘的城堡送給幼兒園里漂亮的女孩子們，這樣可以增加他的好感度。為了公平起見，他決定把送給每個女孩子一樣高的城堡，這樣可以避免女孩子們?yōu)榱双@得更漂亮的城堡而引起爭執(zhí)。可是他發(fā)現(xiàn)自己在壘城堡的時候并沒有預(yù)先考慮到這一點。所以他現(xiàn)在要改造城堡。由于他沒有多余的積木了，他靈機(jī)一動，想出了一個巧妙的改造方案。他決定從每一個城堡中挪去一些積木，使得最終每座城堡都一樣高。為了使他的城堡更雄偉，他覺得應(yīng)該使最后的城堡都盡可能的高。
任務(wù)：
請你幫助小XC編一個程序，根據(jù)他壘的所有城堡的信息，決定應(yīng)該移去哪些積木才能獲得最佳的效果。

輸入數(shù)據(jù)
第一行是一個整數(shù) N (N≤100)， 表示一共有幾座城堡。以下 N 行每行是一系列非負(fù)整數(shù)，用一個空格分隔，按從下往上的順序依次給出一座城堡中所有積木的棱長。用-1結(jié)束。一座城堡中的積木不超過100塊，每塊積木的棱長不超過100。
輸出數(shù)據(jù)
一個整數(shù)，表示最后城堡的最大可能的高度。如果找不到合適的方案，則輸出 0 。
樣例輸入
2
2 1 –1
3 2 1 –1
樣例輸出
3
樣例說明
原數(shù)據(jù)有誤,不知我修正后是不是對?

---

Problem C. 積木城堡

時間限制 1000 ms
內(nèi)存限制 128 MB
題目描述
XC的兒子小XC最喜歡玩的游戲用積木壘漂亮的城堡。城堡是用一些立方體的積木壘成的，城堡的每一層是一塊積木。小XC是一個比他爸爸XC還聰明的孩子，他發(fā)現(xiàn)壘城堡的時候，如果下面的積木比上面的積木大，那么城堡便不容易倒。所以他在壘城堡的時候總是遵循這樣的規(guī)則。
小XC想把自己壘的城堡送給幼兒園里漂亮的女孩子們，這樣可以增加他的好感度。為了公平起見，他決定把送給每個女孩子一樣高的城堡，這樣可以避免女孩子們?yōu)榱双@得更漂亮的城堡而引起爭執(zhí)。可是他發(fā)現(xiàn)自己在壘城堡的時候并沒有預(yù)先考慮到這一點。所以他現(xiàn)在要改造城堡。由于他沒有多余的積木了，他靈機(jī)一動，想出了一個巧妙的改造方案。他決定從每一個城堡中挪去一些積木，使得最終每座城堡都一樣高。為了使他的城堡更雄偉，他覺得應(yīng)該使最后的城堡都盡可能的高。
任務(wù)：
請你幫助小XC編一個程序，根據(jù)他壘的所有城堡的信息，決定應(yīng)該移去哪些積木才能獲得最佳的效果。

輸入數(shù)據(jù)
第一行是一個整數(shù) N (N≤100)， 表示一共有幾座城堡。以下 N 行每行是一系列非負(fù)整數(shù)，用一個空格分隔，按從下往上的順序依次給出一座城堡中所有積木的棱長。用-1結(jié)束。一座城堡中的積木不超過100塊，每塊積木的棱長不超過100。
輸出數(shù)據(jù)
一個整數(shù)，表示最后城堡的最大可能的高度。如果找不到合適的方案，則輸出 0 。
樣例輸入
2
2 1 –1
3 2 1 –1
樣例輸出
3
樣例說明
原數(shù)據(jù)有誤,不知我修正后是不是對?
快速冪+快速矩陣乘（這個寫的太絕了)

long c=10000007; public long divide(long a, long b) {if (b == 0)return 1;else if (b % 2 == 0) //偶數(shù)情況return divide((a % c) * (a % c), b / 2) % c;else//奇數(shù)情況return a % c * divide((a % c) * (a % c), (b - 1) / 2) % c;}

總結(jié)

以上是生活随笔為你收集整理的算法——动态规划2的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。