[動態規劃]OI練習題：取數字遊戲 number

Title: 取數字遊戲【試題連結】

Input: number.in

Output: number.out

Time Limit: 1000 ms

Memory Limit: 128 MB

Level: ★☆

【問題描述】

給定 M*N 的矩陣，其中的每個元素都是 -10 到 10 之間的整數。你的任務是從左上角（ 1 ， 1 ）走到右下角（ M ， N ），每一步只能向右或向下，並且不能走出矩陣的範圍。你所經過的方格裏面的數字都必須被選取，請找出一條最合適的道路，使得在路上被選取的數字之和是儘可能小的正整數。

【輸入格式】

第一行兩個整數 M ， N ，（ 2<=M,N<=20 ），分別表示矩陣的行和列的數目。

接下來的 M 行，每行包括 N 個整數，就是矩陣中的每一行的 N 個元素。

【輸出格式】

僅一行一個整數，表示所選道路上數字之和所能達到的最小的正整數。如果不能達到任何正整數就輸出 -1 。

【輸入輸出樣例】

輸入：

number.in

2 2

0 2

1 0

輸出：

number.out

1

【分析】

狀態表示

如果我們用f[i][j]表示從(1,1)開始按照題目要求走到達(i,j)位置，能取得的最小數字之和。

則按照允許的行走的方式“每一步只能夠向右或者向下”，容易推導出轉移方程:

f[i][j] = min{f[i-1][j],f[i][j-1]}+number[i][j]

這樣我們可以計算出f[m][n]即：“從(1,1)開始走到達(m,n)位置，能取得的最小數字之和”

然而注意到題目要求的是“被選取的數字之和是儘可能小的正整數”而這跟“儘可能小的數”不同。（有可能求出負數和）

注意到這個問題之後，我們可能會修改狀態表示爲：

用f[i][j]表示從(1,1)開始按照題目要求走到達(i,j)位置，能取得的最小正整數之和。

這樣表示後，問題的答案便是f[m][n]了，然而新的問題又產生了：如何進行狀態轉移？

爲了計算f[i][j]，我們希望知道這樣的信息：其左/上邊能取到的，與number[i][j]的和爲正整數的,最小值是多少

於是需要知道到達(i,j)位置的路徑和，都有哪些值？

新狀態表示：布爾數組g[i][j][k]表示從(1,1)開始按照題目要求走到達(i,j)位置，能否使得路徑上的和爲k。

於是問題的解變爲：min{k} st. g[m][n][k] = true

考慮該數組的第三維：k的範圍

“每個元素都是-10到10之間的整數”而且”2<=M<=20, 2<=N<=20”

而從起點到終點一定是剛好取M+N-1個數字。

故k最小爲-10 * 39 = -390，最大爲 10 * 390 = 190

考慮到負數不能作爲數組下標，我們可以將k統一平移390。即用0表示-390，用780表示190。

因此，最終我們需要狀態可以用bool g[11][11][780];表示

g[i][j][k]的計算：

令p=number[i][j];

g[i][j][k]=g[i-1][j][k-p]|g[i][j-1][k-p]

編碼實現的時候注意邊界條件(i或j爲0)及負數的處理。

【我的代碼】

=======Code.1 反向遞歸(50分)=====

C++语言: 高亮代码由发芽网提供

01 /*
02 *Problem:取數字 number
03 *Author: Yee-fan Zhu
04 *Method: Dynamic Programming
05 *Website: http://blog.yeefanblog.tk/
06 *Data: Jan 28,2012
07 */
08 #include <iostream>
09 #include <cstdio>
10 #include <cstdlib>
11 using namespace std;
12 const int MAXN=21;
13 const int SHIFT=380;
14
15 int N,M;
16 bool OK[MAXN][MAXN][SHIFT*2];
17 int Num[MAXN][MAXN];
18
19
20 bool Recursion(int x,int y,int v)
21 {
22     if(OK[x][y][v])
23         return true;
24
25     if(x>=2 && Recursion(x-1,y,v-Num[x][y]) )
26     {
27         OK[x][y][v]=true;
28         return true;
29     }
30     if(y>=2 && Recursion(x,y-1,v-Num[x][y]) )
31     {
32         OK[x][y][v]=true;
33         return true;
34     }
35     return false;
36 }
37
38 int main()
39 {
40     freopen("number.in","r",stdin);
41     freopen("number.out","w",stdout);
42     scanf("%d %d\n",&M,&N);
43     for (int i=1;i<=M;i++)
44         for (int j=1;j<=N;j++)
45             scanf("%d",&Num[i][j]);
46    
47     OK[1][1][Num[1][1]+SHIFT]=true;
48    
49     for(int i=1;i<=SHIFT*2;i++)
50         OK[M][N][i]=Recursion(M,N,i);
51     for (int i=1+SHIFT;i<=SHIFT*2;i++)
52     {
53         if(OK[M][N][i])
54         {
55             printf("%d\n",i-SHIFT);
56             return 0;
57         }
58     }
59     printf("-1\n");
60     return 0;
61 }

======Code.2 正向遞推(100分)======
裸代碼RawCode

C++语言: Codee#25400

01 /*
02 *Problem: 動態規劃 取數字遊戲 number
03 *Author: Yee-fan Zhu
04 *Website: http://blog.yeefanblog.tk/
05 */
06 #include <cstdio>
07 #include <cstdlib>
08 using namespace std;
09
10 int M,N;
11 const int SHIFT=390;
12 bool Available[21][21][SHIFT*2];
13 int Num[21][21];
14
15 void init()
16 {
17     fscanf(stdin,"%d %d\n",&M,&N);
18     for (int i=1;i<=M;i++)
19         for (int j=1;j<=N;j++)
20             fscanf(stdin,"%d",&Num[i][j]);
21     Available[1][1][Num[1][1]+SHIFT]=true;   
22 }
23
24 void dynamic()
25 {
26     for (int i=1;i<=M;i++)
27     {
28         for (int j=1;j<=N;j++)
29         {
30             for (int k=0;k<=SHIFT*2;k++)
31             {
32                 if(Available[i-1][j][k] || Available[i][j-1][k])
33                     Available[i][j][k+Num[i][j]]=true;
34             }
35         }
36     }
37 }
38
39 int main()
40 {
41     freopen("number.in","r",stdin);
42     freopen("number.out","w",stdout);
43     init();
44     dynamic();
45     for (int i=1+SHIFT;i<=SHIFT*2;i++)
46     {
47         if(Available[M][N][i])
48         {
49             fprintf(stdout,"%d\n",i-SHIFT);
50             return 0;
51         }
52     }
53     fprintf(stdout,"-1\n");
54     return 0;
55 }