HzuQZH

用户名：h1810819001

访问量：32318

签　名：

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

　　自我简介：

TA的其他文章

蓝桥杯2017年第八届真题-油漆面积-题解（C++代码）两种解法
浏览：650

蓝桥杯2013年第四届真题-核桃的数量-题解（C语言代码）
浏览：272

小白首选，简单易懂
浏览：247

你可能喜欢

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

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

方格取数——详细的dp算法

　　作者: HzuQZH　　　　发表时间：2019-10-31 09:30:04 浏览：673　|　评论：0　

原题链接：蓝桥杯算法训练VIP-方格取数

题目大意：给定一个矩阵每一个位置有一个权值，从左上角到右下角，要走两次，所到的点如果有权值就取出并变为，求所走路线取值和最大值。
		解题思路：dp算法
	
	解题思路：
		首先假设两条路同时出发，如果相遇在同一个各自就只需要取一次权值。
	
		这里我们来考虑状态：k表示当前所在位置步数（下标和，即x+y），i1表示第一条路线所在位置的行，i2表示第二条路线当前所在位置的行,即dp[k][i][j]。
	因为判断是否在同一个位置的条件就是步数（下标和）相同的请情况下，两条路线在同一行，那么必定在同一列。
	
		现在来考虑状态转移：每一条路线的每一个位置都可以会从他的上方或者他的左边取过来，因为有两条路所以就会有4个状态转移。

上代码：
	
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=27;
int w[N][N],dp[N][N][N];//dp[k][i1][i2]表示在k步数下，第一条路线所在行i1，第二条路线所在行i2
int main(){
	int n,a,b,c;
	cin>>n;
	while(cin>>a>>b>>c,a||b||c){//输入数据
		w[a][b]=c;
	}
	for(int k=2;k<=n+n;k++){//k的取值为2开始，到n+n，因为起点从（1，1）开始，终点为（n,n）
		for(int i1=1;i1<=n;i1++){//枚举每一步数下，第一条路所在行
			for(int i2=1;i2<=n;i2++){//枚举每一步数下，第二条路所在行
				int j1=k-i1,j2=k-i2,t=w[i1][j1];//可由步数和所在行，求出他们所在的列，t为第一条路线所在位置(i1,j1)的权值
				if(j1>=1&&j1<=n&&j2>=1&&j2<=n){//判断所在位置是否合法
					if(i1!=i2)t+=w[i2][j2];//如果不在同一个位置（就加上第二条路上所在位置(i2,j2)的权值）
					//以下为状态转移
					dp[k][i1][i2]=max(dp[k][i1][i2],dp[k-1][i1-1][i2-1]+t);
					//当前这一步可以由上一步时，第一条路线所在位置的左边，第二条路线所在位置的左边转移过来。
					dp[k][i1][i2]=max(dp[k][i1][i2],dp[k-1][i1-1][i2]+t);
					//当前这一步可以由上一步时，第一条路线所在位置的左边，第二条路线所在位置的上边转移过来。
					dp[k][i1][i2]=max(dp[k][i1][i2],dp[k-1][i1][i2-1]+t);
					//当前这一步可以由上一步时，第一条路线所在位置的上边，第二条路线所在位置的左边转移过来。
					dp[k][i1][i2]=max(dp[k][i1][i2],dp[k-1][i1][i2]+t);
					//当前这一步可以由上一步时，第一条路线所在位置的上边，第二条路线所在位置的上边转移过来。

//因为k-1表示为上一步，i1，i2不变可表示上一个位置的j1,j2
				}
			}
		}
	}
	cout<<dp[n+n][n][n]<<endl;//最终状态存放在终点第一条路在n行，，第二条路在n行。
	return 0;
}
```

0.0分

6 人评分

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

HzuQZH

TA的其他文章

你可能喜欢

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

关于逻辑非“！”与取反“~”运算符

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

C二级辅导-公约公倍（C语言代码）

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

方格取数——详细的dp算法

评论区

精彩推荐

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

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

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

钟神赛车（C++代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

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

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

【排队买票】（C语言代码）

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

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

HzuQZH

TA的其他文章

你可能喜欢

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

关于逻辑非“！”与取反“~”运算符

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

C二级辅导-公约公倍 （C语言代码）

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

方格取数——详细的dp算法

评论区

精彩推荐

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

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

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

钟神赛车 （C++代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

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

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

【排队买票】 （C语言代码）

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

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

C二级辅导-公约公倍（C语言代码）

　　评论区

钟神赛车（C++代码）

【排队买票】（C语言代码）