a.第一眼审题看到从左上角走到右下角,dfs
b.再继续看题目,有限定条件:
1.走到一个位置依据已拿宝物的最大价值 maxn 选择是否拿宝
2.只有走到右下角且拿宝数 cnt = k 的路径才有效
c.所以第一步先把左上到右下的深搜写出来
因为待会涉及到一个宝物最大价值 maxn 和拿宝数 cnt 的问题,所以dfs传入四个参数
d. 但是光这样的条件深搜是得不到满分的,所以还得优化
通过对路径位置之间的关系分析我们可以知道:
在四个参数不变的前提之下,这个状态的dfs还是会被计算多次
最简单的情况:
从不同方向到达(x, y)点,如果之前的拿宝数都是cnt - 1,而且 maxn 都要小于 (x, y) 位置的宝物价值a[x][y],那就会重复计算(x, y, a[x][y], cnt)。
更别说有可能在几步之前取宝数达到cnt-1,然后后面几步不拿宝,到 (x, y) 再拿宝到达 cnt 这个数值
e.因此这道题的重复计算是非常恐怖的,我们可以考虑用一个四维数组将已经计算出来的值存下来
这样就可以在到达一个搜索状态的时候,先去判断这个状态是否已经计算,如果计算过就直接返回之前的结果
至于为什么是四维数组,这是因为dfs的参数有四个,四维分别对应 dfs 的四个参数
注意点:因为宝物价值是有可能为 0 的,所以 maxn 的初值设定成了 -1 ,但数组是没有负下标的,因此在记忆的时候选择将 maxn 的下标 +1,通过偏移量来解决数组越界问题
具体的实现看代码吧~
Code:#include
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
//基本变量
int n, m, k;
//记忆数组,输入数组
ll vis[51][51][15][13], a[55][55];
//记忆化搜索
ll dfs(int x, int y, int maxn, int cnt)
{
ll res = 0;
//到达边界或者取宝数大于k
if(x > n || y > m || cnt > k) return 0;
//已经计算过,直接返回
if(vis[x][y][maxn+1][cnt] != -1) return vis[x][y][maxn+1][cnt];
//边界出口
if(x == n && y == m){
if(cnt == k || (cnt == k-1 && a[n][m] > maxn)) return 1;
return 0;
}
//拿或不拿分别两种走法
if(a[x][y] > maxn){
res += dfs(x+1, y, a[x][y], cnt+1);
res += dfs(x, y+1, a[x][y], cnt+1);
}
res += dfs(x+1, y, maxn, cnt);
res += dfs(x, y+1, maxn, cnt);
//结果记忆并返回
return vis[x][y][maxn+1][cnt] = res % mod;
}
int main(void)
{
memset(vis, -1, sizeof(vis));
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++)
scanf("%d", &a[i][j]);
}
cout <
最后附上蓝桥杯汇总链接:蓝桥杯C/C++A组省赛历年真题题解
声明:图片均来源于蓝桥杯官网,以个人刷题整理为目的,如若侵权,请联系删除~
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)