| 等 级 | |
| 排 名 | 47 |
| 经 验 | 11187 |
| 参赛次数 | 5 |
| 文章发表 | 56 |
| 年 龄 | 24 |
| 在职情况 | 在职 |
| 学 校 | 四川工商学院 |
| 专 业 | 通信工程 |
自我简介：
C语言 蓝桥杯 ACM 新人 欢迎大佬 前来指导 交流 本人 博客https://fivecc.blog.csdn.net/
TA的其他文章
你可能喜欢
C语言程序设计教程（第三版）课后习题1.5 （C语言代码）浏览：748 |
C语言程序设计教程（第三版）课后习题8.8 （C++代码）浏览：604 |
【计算两点间的距离】 （C语言代码）浏览：883 |
C语言程序设计教程（第三版）课后习题5.4 （C语言代码）浏览：893 |
输出正反三角形 （C语言代码）浏览：788 |
原题链接：蓝桥杯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分
8 人评分
TheMagician 2024-03-21 23:11:56 |
#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; }
TheMagician 2024-03-21 23:12:29 |
根据答主的思路自己写的，与答主的略有不同