原题链接：蓝桥杯2014年第五届真题-地宫取宝
解题思路:记忆化深搜
注意事项:
参考代码:
#include<stdio.h>
#include <string.h>
int a[51][51];//地宫
long long jl[51][51][15][15];//记录获取数据jl[x][y][此状态最大价值][此状态持宝数];
#define D %1000000007
int n,m,k;
long int cs=0;
long long f(long int x,long int y,long int max,long int sum)
{ int i,j,t,s;
if(x<=n&&y<=m&&sum<=k)//地宫范围 及优化 持宝数超出直接过
{ if(jl[x][y][max][sum]!=-1)return jl[x][y][max][sum];//是否曾记录过
if(x==n&&y==m)//到达出口
{
if(sum==k||(sum==k-1&&max<a[x][y]))//判断 持宝数符合条件或再加上出口宝物 符合
{jl[x][y][max][sum]=1;//记录
return jl[x][y][max][sum];
}
}
else
{
if(a[x][y]>max)//当满足可拿起 条件
{ t=a[x][y]; //此状态 可行方案数 = 拿起后向右 + 不拿起后向右 + 拿起后向右下 + 不拿起后向下
jl[x][y][max][sum]=f(x+1,y,t,sum+1)D+f(x+1,y,max,sum)D+f(x,y+1,t,sum+1)D+f(x,y+1,max,sum)D;
}
else jl[x][y][max][sum]=f(x+1,y,max,sum)D+f(x,y+1,max,sum)D;//当不满足可拿起 条件
//此状态 可行方案数 = 不拿起后向右 + 不拿起后向下
return jl[x][y][max][sum]D;
}
}
return jl[x][y][max][sum]=0;
}
int main()
{int i,j;
memset(jl,-1,sizeof(jl));//此处一定不能标记为 0 因为可能会无解
scanf("%d%d%d",&n,&m,&k);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{scanf("%d",&a[i][j]);
a[i][j]++;
}
printf("%lld\n",f(1,1,0,0));
return 0;
}0.0分
5 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
@TheMagician #include <stdio.h> #include <string.h> #define D %1000000007 int n, m, k, a[52][52]; long int b[52][52][14][14];//x,y,max,number int go[2][2] = { {0,1},{1,0} }; long long int dfs(int x, int y, int max, int number); int main(void) { int i, j; scanf("%d%d%d", &n, &m, &k); for (i = 1; i <= n; i++) { for (j = 1; j <= m; j++) { scanf("%d", &a[i][j]); } } memset(b,-1,sizeof(b)); printf("%lld",dfs(1,1,-1,0)); return 0; } long long int dfs(int x, int y, int max, int number) { if(b[x][y][max][number]!=-1) {return b[x][y][max][number];} b[x][y][max][number]=0; if(x==n&&y==m) { if ((number == k - 1 && a[n][m] > max) || (number == k)) { b[x][y][max][number]=1;return 1;} return 0; } for (int i = 0; i <= 1&&number<=k; i++) { if (x + go[i][0] <= n && y + go[i][1] <= m) { if(a[x][y]>max) {b[x][y][max][number]+=dfs(x + go[i][0], y + go[i][1], a[x][y], number+1)D +dfs(x + go[i][0], y + go[i][1], max, number)D;} else {b[x][y][max][number]+=dfs(x + go[i][0], y + go[i][1], max, number)D;} } } return b[x][y][max][number]D; }