#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; int g[100][100]; int d[100][100][50][50]; int n,m,k; int dp(int x,int y,int num,int big){ if(d[x][y][num][big]!=-1) return d[x][y][num][big]; d[x][y][num][big]=0; if(x==n&&y==m&&k==num) d[x][y][num][big]=1; if(g[x][y]>big&&k>num) { d[x][y][num][big]+=dp(x,y,num+1,g[x][y]); d[x][y][num][big]%=1000000007; } if(x<n) { d[x][y][num][big]+=dp(x+1,y,num,big); d[x][y][num][big]%=1000000007; } if(y<m) { d[x][y][num][big]+=dp(x,y+1,num,big); d[x][y][num][big]%=1000000007; } return d[x][y][num][big]; } int main(void){ cin>>n>>m>>k; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ cin>>g[i][j]; g[i][j]++; } memset(d,-1,sizeof(d)); dp(1,1,0,0); cout<<d[1][1][0][0]<<endl; return 0; }
使用了记忆化搜索的方式,但是一开始出现了超时的问题,出现超时间限制的情况如下代码
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; int g[100][100]; int d[100][100][50][50]; int n,m,k; int dp(int x,int y,int num,int big){ if(d[x][y][num][big]) return d[x][y][num][big]; d[x][y][num][big]=0; if(x==n&&y==m&&k==num) d[x][y][num][big]=1; if(g[x][y]>big&&k>num) { d[x][y][num][big]+=dp(x,y,num+1,g[x][y]); d[x][y][num][big]%=1000000007; } if(x<n) { d[x][y][num][big]+=dp(x+1,y,num,big); d[x][y][num][big]%=1000000007; } if(y<m) { d[x][y][num][big]+=dp(x,y+1,num,big); d[x][y][num][big]%=1000000007; } return d[x][y][num][big]; } int main(void){ cin>>n>>m>>k; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ cin>>g[i][j]; g[i][j]++; } dp(1,1,0,0); cout<<d[1][1][0][0]<<endl; return 0; }
原因是没有使用好记忆化搜索的优势,导致了方法的退化,出现了重复计算的现象
最好的解决方式是
使用一个数组来进行保存是否进行了访问,防止了出错,采用了用空间开换时间的策略
vis[][][][]
没有给出具体的代码,自己实现
0.0分
3 人评分
程序员的表白 (C语言代码)浏览:661 |
母牛的故事 (C语言代码)浏览:715 |
字符逆序 (C语言代码)浏览:614 |
1024题解浏览:807 |
数列排序 (C语言代码)浏览:607 |
小O的图案 (C语言代码)浏览:913 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:545 |
母牛的故事 (C语言代码)浏览:478 |
C语言程序设计教程(第三版)课后习题8.4 (C++代码)浏览:448 |
母牛的故事 (C语言代码)浏览:499 |