[dp] 蓝桥杯 地宫取宝

时间:2022-09-09 23:14:12

题意:

中文题而且很短就不说了~

思路:

四维dp[i][j][l][o] 代表在(i,j)这个位置,拿了o个宝贝,所有宝贝最大值是l的方案数。

因为宝贝的价值是0~12 我们的初始状态要是0,所以输入的时候把每个宝贝的价值加1.

然后对于每个点,都会有一个不拿的状态,和一个可能拿的状态。

直接转换下去就OK了。

代码:

#include"stdio.h"
#include"algorithm"
#include"string.h"
#include"map"
#include"iostream"
#include"queue"
#include"string"
#define mod 1000000007
using namespace std;
int dp[55][55][14][14],mp[55][55];
int main()
{
int n,m,k;
while(scanf("%d%d%d",&n,&m,&k)!=-1)
{
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
scanf("%d",&mp[i][j]);
mp[i][j]++;
}
}
memset(dp,0,sizeof(dp));
dp[0][0][mp[0][0]][1]=1;
dp[0][0][0][0]=1;
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
for(int l=0; l<=13; l++)
{
for(int o=0; o<=k; o++)
{
if(dp[i][j][l][o]==0) continue;
if(mp[i][j+1]>l)
{
dp[i][j+1][mp[i][j+1]][o+1]+=dp[i][j][l][o];
dp[i][j+1][mp[i][j+1]][o+1]%=mod;
}
if(mp[i+1][j]>l)
{
dp[i+1][j][mp[i+1][j]][o+1]+=dp[i][j][l][o];
dp[i+1][j][mp[i+1][j]][o+1]%=mod;
}
dp[i][j+1][l][o]+=dp[i][j][l][o];
dp[i][j+1][l][o]%=mod;
dp[i+1][j][l][o]+=dp[i][j][l][o];
dp[i+1][j][l][o]%=mod;
}
}
}
}
int ans=0;
for(int i=0; i<=13; i++)
{
ans=(ans+dp[n-1][m-1][i][k])%mod;
}
printf("%d\n",ans);
}
return 0;
}