题解 1611: 蓝桥杯算法训练VIP-传纸条

来看看其他人写的题解吧!要先自己动手做才会有提高哦! 
返回题目 | 我来写题解

筛选

传纸条——dp算法详解

**这个题,可以先跳至1639题(方格取数)看一下**题目大意:给定一个矩阵每一个位置有一个权值,从左上角到右下角,要走两次,所到的点如果有权值就取出并变为0,求所走路线取值和最大值。解题思路:这题和方格取数的题可以说是同样的题目,只不过这里题目的意思是从起点到终点,再由终点到起点。

蓝桥杯算法训练VIP-传纸条-题解(C++代码)

#四维dp**思路:设f[i][j][k][l]为从(0,0)位置由两条不交叉的线路走到(i,j),(k,l)位置时的最大好感度和,则它的上一步可能有四种情况:第一个点由上走来,第二个点也由上走来,此时的好感度和为f[i-1][j][k-1][l]+a[i][j]+a[k][l]第一个点由上走来,