HzuQZH

用户名：h1810819001

访问量：32324

签　名：

等　　级
排　　名	45
经　　验	12277
参赛次数	7
文章发表	69
年　　龄	0
在职情况	学生
学　　校	贺州学院
专　　业

　　自我简介：

TA的其他文章

数据结构-KMP字符串模式匹配算法实现-题解(C++代码)
浏览：504

数据结构-用数组实现堆排（易处理，容易理解）
浏览：634

区间dp（动归思想）
浏览：938

你可能喜欢

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

蓝桥杯2014年第五届真题-地宫取宝-题解（C语言代码）

　　作者: HzuQZH　　　　发表时间：2020-10-09 15:21:01 浏览：414　|　评论：0　

原题链接：蓝桥杯2014年第五届真题-地宫取宝

### 解题思路：动态规划。在每一个位置的状态考虑，当前这个位置的状态是由哪些状态转移过来的。
<br>

### dp[i][j][u][v]表示在(i,j)这个位置，拿到u个物品，且这些物品的最大价值是v。
<br>

### 我们可以考虑当前位置(i,j)拿不拿当前这个物品，如果不拿那么可以从dp[i-1][j][u][v]、dp[i][j-1][u][v]转移过来，表示上一个位置已经拿到了u个物品最大价值为v的。如果拿则可以从dp[i-1][j][u-1][c]、dp[i][j-1][u-1][c]转移过来，表示上一个位置拿了u-1个，并且最大价值为c(c为小于v的数)，最后再把最后手上可能拿的价值的方案数加起来即可。
<br>

### ps：因为这道题的所有物品价值范围是0…120…12，可以把他们全部都递增，范围就变成了1…131…13，因为我们记录的是方案数，只关心各个物品之间的大小关系，具体数值不影响答案，但是这样的做法可以把00作为一个特殊边界来处理

```cpp
#include<bits/stdc++.h>
#define x first
#define y second
#define mem(h) memset(h,-1,sizeof h)
#define mcp(a,b) memcpy(a,b,sizeof b)
using namespace std;
typedef long long LL;
typedef unsigned long long ull; 
typedef pair<int,int>PII;
typedef pair<double,double>PDD;
namespace IO{
	inline LL read(){
		LL o=0,f=1;char c=getchar();
		while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
		while(c>='0'&&c<='9'){o=o*10+c-'0';c=getchar();}
		return o*f;
	}
}using namespace IO;
//#############以上是自定义技巧（可忽略）########## 
const int N=50+7,M=2e5+7,INF=0x3f3f3f3f,mod=1e9+7,P=131;
int dp[N][N][13][14]; 
int n,m,k;
int w[N][N];
int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>w[i][j];
			w[i][j]++;//这里是需要注意的点，把所有的权值+1，更好处理也不影响结果
		}
	}
	dp[1][1][1][w[1][1]]=1;//如果拿起(1,1)的物品
	dp[1][1][0][0]=1;//如果不拿
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(i==1&&j==1)continue;//这个位置可以跳过
			for(int u=0;u<=k;u++){//枚举到达当前位置可能拿了几个物品
				for(int v=0;v<=13;v++){//枚举到达当前位置手中的最大物品价值
					int &val=dp[i][j][u][v];
					val=(val+dp[i-1][j][u][v])%mod;//不拿当前位置的物品时可能从这些状态转移过来
					val=(val+dp[i][j-1][u][v])%mod;
					if(u>0&&v==w[i][j]){//如果到达当前位置手中有物品，并且物品最大价值等于当前位置的物品价值，那么可以拿起当前物品
						for(int c=0;c<v;c++){//可以从这些状态转移过来
							val=(val+dp[i-1][j][u-1][c])%mod;
							val=(val+dp[i][j-1][u-1][c])%mod;
						}
					} 
				}
			}
		}
	}
	int res=0;
	for(int i=0;i<=13;i++){
		res=(res+dp[n][m][k][i])%mod;//把最后手上可能拿的最大价值方案数相加
	}
	cout<<res<<endl;
	return 0;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

HzuQZH

TA的其他文章

你可能喜欢

Pascal三角（Java代码）

C语言训练-立方和不等式（C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C二级辅导-等差数列（C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

蓝桥杯2014年第五届真题-地宫取宝-题解（C语言代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题9.4 （Java代码）

A+B for Input-Output Practice (VII) （C++代码）

Pascal三角（C语言代码）

计算质因子（C++代码）

WU-格式化数据输出（C语言代码）

1128题解（返回值为数组的情况）

矩阵乘方（C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

复数求和（C语言代码）

HzuQZH

TA的其他文章

你可能喜欢

Pascal三角 （Java代码）

C语言训练-立方和不等式 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C二级辅导-等差数列 （C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

蓝桥杯2014年第五届真题-地宫取宝-题解（C语言代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题9.4 （Java代码）

A+B for Input-Output Practice (VII) （C++代码）

Pascal三角 （C语言代码）

计算质因子 （C++代码）

WU-格式化数据输出 （C语言代码）

1128题解（返回值为数组的情况）

矩阵乘方 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

复数求和 （C语言代码）

Pascal三角（Java代码）

C语言训练-立方和不等式（C语言代码）

C二级辅导-等差数列（C语言代码）

　　评论区

Pascal三角（C语言代码）

计算质因子（C++代码）

WU-格式化数据输出（C语言代码）

矩阵乘方（C语言代码）

复数求和（C语言代码）