地下宫殿的宝藏(蓝桥问题)
最编程
2024-04-13 14:29:04
...
描述
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取模的结果。
输入样例 1
2 2 2
1 2
2 1
输出样例 1
2
思路
动态规划,思维dp,f[i][j][t][p]存储从起点走到(i,j)点,已经拿到t个物品,且最大值为p的方案集合,存储性质为方案的个数(闫氏dp分析)
写出状态转移方程(分两种情况,一种是不取C[i][j]这个物品,另一种是取了,前提为p==C[i][j])
f[i][j][t][p]=f[i-1][j][t][p]+f[i][j-1][t][p]
f[i][j][t][p]+=f[i-1][j][t-1][1]+......f[i-1][j][t-1][p-1] +f[i][j-1][t-1][1]+......f[i][j-1][t-1][p-1]
#include<iostream>
#include<string.h>
using namespace std;
#define MOD 1000000007
using ll = long long;
const int M=15;
int n,m,k;
int C[51][51]={0};
int f[51][51][15][15];
//所有从起点走到(i,j)点,已经拿到t个宝物,且最大值为p的方案集合
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{//这里对物品价值设置一个偏移量,因为题目设定物品价值可能为0
cin>>C[i][j];C[i][j]++;
}//设置偏移量后,价值为0代表分界点
}
f[1][1][0][0]=1;
f[1][1][1][C[1][1]]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int t=0;t<=k;t++)
for(int p=0;p<M;p++)
{
//不拿物品
f[i][j][t][p]=(f[i][j][t][p]+f[i-1][j][t][p])%MOD;
f[i][j][t][p]=(f[i][j][t][p]+f[i][j-1][t][p])%MOD;
//可以拿物品
if(t>0&&C[i][j]==p)
{
for(int s=0;s<p;s++)
{
f[i][j][t][p]=(f[i][j][t][p]+f[i-1][j][t-1][s])%MOD;
f[i][j][t][p]=(f[i][j][t][p]+f[i][j-1][t-1][s])%MOD;
}
}
}
int res=0;
for(int p=1;p<M;p++)
{
res=(res+f[n][m][k][p])%MOD;
}
cout<<res<<endl;
return 0;
}
推荐阅读
-
蓝桥杯:日期问题(我的无奈之问)
-
蓝桥杯问题第16省Ca6 - 寒假作业(全排列问题) 现在的小学数学题没那么好玩了。来看看这份寒假作业吧:□ + □ = □ □ - □ = □ □□ × □ = □ □ ÷ □ = □ 每个平方的代入法
-
地下宫殿的宝藏(蓝桥问题)
-
备战 "蓝桥杯"--与数论有关的问题
-
蓝桥杯每日一题 ------ 背包问题(四)--数的分解
-
蓝桥杯竞赛中的T(动态规划)问题解决 - C语言实践指南
-
蓝桥杯日常挑战 - 背包问题(二):二维成本的背包优化问题
-
蓝桥杯比赛题目1110:巧用排列组合与高精度计算解决2的k次方进制数问题
-
蓝桥杯实战题目解析:飞机降落问题的DFS算法实现
-
蓝桥杯历年试题:连号区间数问题的运行超时情况