X 國王有一個地宮寶庫，是 n×m 個格子的矩陣，每個格子放一件寶貝，每個寶貝貼著價值標簽。

地宮的入口在左上角，出口在右下角。

小明被帶到地宮的入口，國王要求他只能向右或向下行走。

走過某個格子時，如果那個格子中的寶貝價值比小明手中任意寶貝價值都大，小明就可以拿起它（當然，也可以不拿）。

當小明走到出口時，如果他手中的寶貝恰好是 k 件，則這些寶貝就可以送給小明。

請你幫小明算一算，在給定的局面下，他有多少種不同的行動方案能獲得這 k 件寶貝。

輸入格式
第一行 3 個整數，n,m,k，含義見題目描述。

接下來 n 行，每行有 m 個整數 Ci 用來描述寶庫矩陣每個格子的寶貝價值。

輸出格式
輸出一個整數，表示正好取 k 個寶貝的行動方案數。

該數字可能很大，輸出它對 1000000007 取模的結果。

數據范圍
1≤n,m≤50,
1≤k≤12,
0≤Ci≤12
輸入樣例1：
2 2 2
1 2
2 1
輸出樣例1：
2
輸入樣例2：
2 3 2
1 2 3
2 1 5
輸出樣例2：
14

解題思路：
首先我們定義dp[i][j][cnt][k]表示小明從左上角走到(i,j)拿了cnt個物品且手上最大價值為k的走法，在這道題當中價值的范圍為(0,12),意思就是在地圖的各個點的物品都有可能價值是0，所以我們在讀入數據的時候，將每個數據都+1，這樣價值的范圍就變成了(1,13)，方便我們考慮初始化問題，然后我們想想關系表達式，在這個點可以取或者不取，不取的話，代碼如下：

dp[i][j][cnt][v] = (dp[i][j][cnt][v] + dp[i - 1][j][cnt][v]) % MOD; dp[i][j][cnt][v] = (dp[i][j][cnt][v] + dp[i][j - 1][cnt][v]) % MOD;

這里要分開寫，而且結果要%MOD，不然會爆數據，然后小明每次取的物品比前面的物品都要大，然后，如果這個點的物品能取，一定符合：
這個點物品的價值等于我們dp[i][j][cnt][k]中的k值，而且如果取物品，那么cnt一定大于0，然后我們要考慮怎么初始化，在起點，小明有可能拿這個物品，也有可能不拿這個物品，所以不拿就是dp[1][1][0][0] = 1，拿這個物品dp[1][1][1][w[1][1]]

代碼如下：

#include <iostream> using namespace std; const int N = 55; const int MOD = 1000000007; int dp[N][N][15][15]; int w[N][N]; int n, m, k;int main() {cin >> n >> m >> k;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++) {cin >> w[i][j];w[i][j]++;}dp[1][1][0][0] = 1;dp[1][1][1][w[1][1]] = 1;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)for (int cnt = 0; cnt <= k; cnt++)for (int v = 0; v <= 13; v++) {dp[i][j][cnt][v] = (dp[i][j][cnt][v] + dp[i - 1][j][cnt][v]) % MOD;dp[i][j][cnt][v] = (dp[i][j][cnt][v] + dp[i][j - 1][cnt][v]) % MOD;if (cnt > 0 && w[i][j] == v) {for (int s = 0; s < v; s++) {dp[i][j][cnt][v] = (dp[i][j][cnt][v] + dp[i - 1][j][cnt - 1][s]) % MOD;dp[i][j][cnt][v] = (dp[i][j][cnt][v] + dp[i][j - 1][cnt - 1][s]) % MOD;}}}int res = 0;for (int i = 0; i <= 13; i++) {res = (res + dp[n][m][k][i]) % MOD;}cout << res << endl;return 0;}

總結

以上是生活随笔為你收集整理的[蓝桥杯]地宫取宝的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。