地宫取宝
时间： 1ms 内存：128M
描述：
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 3 2
1 2 3
2 1 5
示例输出：
14提示：
参考答案（内存最优[0]）：
#include<iostream>
#include<string.h>
using namespace std;
long long dp[60][60][15][15];//表示在位置在（n，m）时，手里的物品有k件，手里的物品最大价值为c时到达终点的方法数
int map[60][60];//格子地图
int k,N,M;
void dfs(int n,int m,int k1,int c){
if(dp[n][m][k1][c]!=-1) return; //已经搜索过的结束递归
dp[n][m][k1][c]=0; //搜索到标记0
if(k1==k&&n==N&&m==M) dp[n][m][k1][c]=1;//搜索到右下角满足条件，可行方案+1
if(map[n][m]>c&&k1<k){ //物件不足K并且遇见比总值大的宝物
dfs(n,m,k1+1,map[n][m]);dp[n][m][k1][c]+=dp[n][m][k1+1][map[n][m]];
dp[n][m][k1][c]%=1000000007;
}
if(n<N) {
dfs(n+1,m,k1,c);dp[n][m][k1][c]+=dp[n+1][m][k1][c];
dp[n][m][k1][c]%=1000000007;
}
if(m<M){
dfs(n,m+1,k1,c);dp[n][m][k1][c]+=dp[n][m+1][k1][c];
dp[n][m][k1][c]%=1000000007;
}
}
int main(){
cin>>N>>M>>k;
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++){
cin>>map[i][j];map[i][j]++;//地图每个格子的数值加一
}
}
memset(dp,-1,sizeof(dp));//初始化为-1
dfs(1,1,0,0);//从地图最左上角开始，手里的物件数为0，总价值为0
cout<<dp[1][1][0][0]<<endl;//输出最终的叠加值
return 0;
}参考答案（时间最优[0]）：
#include<iostream>
using namespace std;
int n,m,k;
int cnt=0;
int a[1000][1000];
int dfs(int x,int y,int own,int times)
{
int best=own;
if(x==n-1&&y==m-1)
{
if(times==k)
{
cnt++;
}
if(times==k-1&&a[x][y]>best)
{
cnt++;
}
return 0;
cnt=cnt%1000000007;
}
else
{
if(a[x][y]>best)
{
if(x+1!=n)
{
dfs(x+1,y,a[x][y],times+1);
dfs(x+1,y,own,times);
}
if(y+1!=m)
{
dfs(x,y+1,a[x][y],times+1);
dfs(x,y+1,own,times);
}
}
else
{
if(x+1!=n)
{
dfs(x+1,y,own,times);
}
if(y+1!=m)
{
dfs(x,y+1,own,times);
}
}
}
return 0;
}
int main(){
cin>>n>>m>>k;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>a[i][j];
}
}
int own=0;
int times=0;
dfs(0,1,own+a[0][0],times+1);
dfs(1,0,own+a[0][0],times+1);
dfs(0,1,own,times);
dfs(1,0,own,times);
cout<<cnt<<endl;
}题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。