题目
好像就普通的记忆化搜索，不过有一些东西注意一下就好了。
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #define int long long using namespace std; const int mod=1000000007*1LL; int a[55][55],f[55][55][15][15],n,m,k; int dfs(int x,int y,int maxx,int ji) { if(f[x][y][maxx][ji]!=-1)return f[x][y][maxx][ji];//为什么初始化要-1呢，可能某一个点的答案就是0，要是不等于0返回，可能会进入某一个点多次，然后tle if(ji<0)return 0; if(x<1||x>n||y<1||y>m)return 0; if(x==n&&y==m) { if(ji==0)return 1; else if(ji==1&&a[x][y]>maxx)return 1; else return 0; } int sum=0; if(a[x][y]>maxx) { sum=(sum%mod+dfs(x+1,y,a[x][y],ji-1)%mod)%mod; sum=(sum%mod+dfs(x,y+1,a[x][y],ji-1)%mod)%mod; } sum=(sum%mod+dfs(x+1,y,maxx,ji)%mod)%mod; sum=(sum%mod+dfs(x,y+1,maxx,ji)%mod)%mod; return f[x][y][maxx][ji]=sum; } signed main() { cin>>n>>m>>k; memset(f,-1,sizeof(f)); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf("%lld",&a[i][j]); a[i][j]++;//因为价值有0，所以第三维初始化要为-1，这样不行，所以直接所有+1，因为答案只跟数字大小有关，所以这样做是可以的 } } dfs(1,1,0,k); cout<<f[1][1][0][k]; }