題目

X 國王有一個地宮寶庫。是 n x m 個格子的矩陣。每個格子放一件寶貝。每個寶貝貼著價值標簽。地宮的入口在左上角，出口在右下角。小明被帶到地宮的入口，國王要求他只能向右或向下行走。走過某個格子時，如果那個格子中的寶貝價值比小明手中任意寶貝價值都大，小明就可以拿起它（當然，也可以不拿）。當小明走到出口時，如果他手中的寶貝恰好是k件，則這些寶貝就可以送給小明。請你幫小明算一算，在給定的局面下，他有多少種不同的行動方案能獲得這k件寶貝。

【數據格式】

輸入一行3個整數，用空格分開：n m k (1<=n,m<=50, 1<=k<=12)接下來有 n 行數據，每行有 m 個整數 Ci (0<=Ci<=12)代表這個格子上的寶物的價值要求輸出一個整數，表示正好取k個寶貝的行動方案數。該數字可能很大，輸出它對 1000000007 取模的結果。例如，輸入： 2 2 2 1 2 2 1 程序應該輸出： 2再例如，輸入： 2 3 2 1 2 3 2 1 5 程序應該輸出： 14資源約定： 峰值內存消耗 < 256M CPU消耗 < 1000ms請嚴格按要求輸出，不要畫蛇添足地打印類似：“請您輸入...” 的多余內容。所有代碼放在同一個源文件中，調試通過后，拷貝提交該源碼。注意: main函數需要返回0 注意: 只使用ANSI C/ANSI C++ 標準，不要調用依賴于編譯環境或操作系統的特殊函數。 注意: 所有依賴的函數必須明確地在源文件中 #include <xxx>， 不能通過工程設置而省略常用頭文件。提交時，注意選擇所期望的編譯器類型。

代碼

#include <iostream> #include <cstring>using namespace std; const int MOD = 1000000007; int n, m, k; int data[50][50];long long ans; long long cache[50][50][14][13];void dfs(int x, int y, int max, int cnt) {if (x == n || y == m || cnt > k)return;int cur = data[x][y];if (x == n - 1 && y == m - 1)//已經面臨最后一個格子{if (cnt == k || (cnt == k - 1 && cur > max)) {ans++;if (ans > MOD)ans %= MOD;}}if (cur > max) {//可以取這個物品dfs(x, y + 1, cur, cnt + 1);dfs(x + 1, y, cur, cnt + 1);}//對于價值較小，或者價值大但不去這個物品的情況如下dfs(x, y + 1, max, cnt);dfs(x + 1, y, max, cnt);}long long dfs2(int x, int y, int max, int cnt) { // 查緩存if (cache[x][y][max+1][cnt] != -1)return cache[x][y][max+1][cnt];long long ans = 0;if (x == n || y == m || cnt > k)return 0;int cur = data[x][y];if (x == n - 1 && y == m - 1)//已經面臨最后一個格子{if (cnt == k || (cnt == k - 1 && cur > max)) {ans++;if (ans > MOD)ans %= MOD;}return ans;}if (cur > max) {//可以取這個物品ans += dfs2(x, y + 1, cur, cnt + 1);ans += dfs2(x + 1, y, cur, cnt + 1);}//對于價值較小，或者價值大但不去這個物品的情況如下ans += dfs2(x, y + 1, max, cnt);ans += dfs2(x + 1, y, max, cnt);cache[x][y][max+1][cnt]=ans % MOD;return cache[x][y][max+1][cnt]; }int main(int argc, const char *argv[]) {scanf("%d %d %d", &n, &m, &k);for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {scanf("%d", &data[i][j]);}} // dfs(0, 0, -1, 0);//第一個點的價值可能是0 // printf("%d\n", ans); memset(cache,-1, sizeof(cache));printf("%lli\n", dfs2(0, 0, -1, 0));return 0; }

總結

以上是生活随笔為你收集整理的征战蓝桥 —— 2014年第五届 —— C/C++A组第8题——地宫取宝的全部內容，希望文章能夠幫你解決所遇到的問題。

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