[dp] 蓝桥杯 地宫取宝

题意：

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

思路：

四维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 1000000007using 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;}

这种精神使人能在旅行中和大自然更加接近，