目录

• 题目描述
• • 输入
  • 输出
  • 样例输入
  • 样例输出
  • 题目分析
  • 详细代码
  • 测试结果
  • 附加代码

题目描述

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 3 2
1 2 3
2 1 5

样例输出

14

题目分析

拿到这个题目，第一时间想到的是dfs，于是就尝试先试着做，按照框架套，判断结束的条件：
1.到达出口并且拿到的宝物为k件
2.到达出口并且拿到的宝物为k-1件，此时宝物的价值要小于出口处格子中的价值（题目要求，并自动判定接下来要拿起出口处的宝物）
若满足条件则可行方法加1，这里注意要对1000000007取模，不同的题目要求不同。若不满足条件则继续进行判断：
1.如果当前的横坐标未到达最右边（边界）：
11.如果当前格子中的宝物价值大于目前所有已拿宝物中格子的价值，则目标向右移动一格并且拿上该宝物，总携带数量加1，并且记目前已拿宝物最大价值为此格子中宝物的价值。
12.如果当前格子中的宝物价值小于目前所有已拿宝物中格子的价值，则目标向右移动一格，其余不变。
2.纵坐标同理，此处不再赘述。
核心部分就是这些，最后只需要将dfs都初始化为0即可。

详细代码

#include <iostream>
using namespace std;int n, m, k, sum = 0;
int map[100][100];void dfs(int x, int y, int c, int v)
{if (x == n - 1 && y == m - 1){if (c == k || (c == k - 1 && v < map[x][y])){sum %= 1000000007;sum++;return;}}else{if (x < n - 1){if (v < map[x][y])dfs(x + 1, y, c + 1, map[x][y]);dfs(x + 1, y, c, v);}if (y < m - 1){if (v < map[x][y])dfs(x, y + 1, c + 1, map[x][y]);dfs(x, y + 1, c, v);}}
}int main()
{cin >> n >> m >> k;for (int i = 0; i < n; i++){for (int j = 0; j < m; j++)cin >> map[i][j];}dfs(0, 0, 0, 0);cout << sum << endl;return 0;
}

测试结果

可以发现运行时间不满足要求，后在网上查询发现可以用到记忆化搜索，大致就是加上一个备忘录。（dp和dsf联合起来使用）

附加代码

供参考

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int MOD = 1000000007;
int M[55][55];
int dp[55][55][15][15];
int n,m,k;
//int sx,sy;
//int ex,ey;
int dir[2][2]={{0,1},{1,0}};//右、下 int dfs(int x,int y,int num,int value){if(dp[x][y][num][value+1]!=-1){//证明之前已经求过了return dp[x][y][num][value+1];} int count = 0;if(x == n&&y==m){if(num == 0||(num == 1 && M[x][y]>value)){//到达最后一步//步数num为0，就返回1；//如果num为1且如果物品价值大于可取价值,证明可以取这最后一个宝物，刚好使num为0，故也返回1 return 1;}} //	cout<<"x:"<for(int i = 0;i < 2;i++){int dx = x + dir[i][0];int dy = y + dir[i][1];if(dx > n||dy > m){//超出地图范围了 continue;}if(M[x][y] > value){count += dfs(dx,dy,num-1,M[x][y]);//取了当前的宝物 }count %= MOD;count += dfs(dx,dy,num,value);//没有取当前的宝物count %= MOD;}return dp[x][y][num][value+1] = count;//因为value值初始是负数，故需要加个一保证是>=0的数 
}int main(){cin>>n>>m>>k;for(int i = 1;i <= n;i++){for(int j = 1;j <= m;j++){cin>>M[i][j];}}memset(dp,-1,sizeof(dp));cout<<dfs(1,1,k,-1)<<endl;//value设置为-1，避免读不到物品价值为0的情况 return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！