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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/266983.html
標籤：其他
上一篇：JG-OJ記錄-第七次線上賽：20-21(2)第0次線上賽（智商康復訓練）
下一篇：陣列的排序（冒泡排序）