历届试题 地宫取宝 蓝桥杯

14

记忆化搜索

难倒不难，就是麻烦。

#include<stdio.h>long long dp[51][51][13][13];//记录子问题long long G[51][51];long long n,m;long long dfs(long long i,long long j,long long k,long long max){long long d;if(dp[i][j][k][max]>=0)return dp[i][j][k][max];//某一点到终点肯定不能取k个物品，dp为0，避免重复运算if(k==0){    if(i==n||j==m){        for(d=0;d<=12;d++)            dp[i][j][k][d]=1;//不取物品的话，路径数只与位置有关        return 1;    }    else{        dp[i][j][k][max]=(dfs(i+1,j,k,max)+dfs(i,j+1,k,max))%1000000007;        for(d=0;d<=12;d++)            dp[i][j][k][d]=dp[i][j][k][max];        return dp[i][j][k][max];    }}if(i==n&&j==m){    if(k==0)        return 1;    else if(k==1){        if(max<G[n][m])            return 1;        else            return 0;    }    else        return 0;}if(i==n){    if(max<G[i][j])        return dp[i][j][k][max]=(dfs(i,j+1,k,max)+dfs(i,j+1,k-1,G[i][j]))%1000000007;    else        return dp[i][j][k][max]=dfs(i,j+1,k,max);}if(j==m){    if(max<G[i][j])        return dp[i][j][k][max]=(dfs(i+1,j,k,max)+dfs(i+1,j,k-1,G[i][j]))%1000000007;    else        return dp[i][j][k][max]=dfs(i+1,j,k,max);}if(max<G[i][j])    return dp[i][j][k][max]=(dfs(i,j+1,k,max)+dfs(i,j+1,k-1,G[i][j])+dfs(i+1,j,k,max)+dfs(i+1,j,k-1,G[i][j]))%1000000007;else    return dp[i][j][k][max]=(dfs(i,j+1,k,max)+dfs(i+1,j,k,max))%1000000007;}int main(){long long i,j,k;scanf("%d%d%d",&n,&m,&k);for(i=1;i<=n;i++)    for(j=1;j<=m;j++)    scanf("%d",&G[i][j]);memset(dp,-1,sizeof(dp));PRintf("%d",dfs(1,1,k,-1));//max取-1，第一格是零的话，取和不取是两种情况return 0;}