/*问题描述 X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。
地宫的入口在左上角，出口在右下角。
小明被带到地宫的入口，国王要求他只能向右或向下行走。
走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大， 小明就可以拿起它（当然，也可以不拿）。
当小明走到出口时，如果他手中的宝贝恰好是k件，则这些宝贝就可以送给小明。
请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这k件宝贝。 输入格式 输入一行3个整数，用空格分开：n m k (1<=n,m<=50, 1<=k<=12)
接下来有 n 行数据，每行有 m 个整数 Ci (0<=Ci<=12)代表这个格子上的宝物的价值 输出格式 要求输出一个整数，表示正好取k个宝贝的行动方案数。该数字可能很大，输出它对 1000000007 取模的结果。 样例输入 2 2 2 1 2 2 1 样例输出 2 样例输入 2 3 2 1 2 3 2 1 5 样例输出 14 思路 ：记忆法深搜
*/
代码语言：javascript复制#include<stdio.h>
#include <string.h>
int a[51][51];//地宫
long long jl[51][51][15][15];//记录获取数据jl[x][y][此状态最大价值][此状态持宝数];
#define D 00000007
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("%lldn",f(1,1,0,0));
return 0;
} 
