暑期集训模拟赛3 (3)

因为从左上到右下要找到两条路径,还不能重合,所以我们直接从左上到右下,开四维数组,前两个和后两个分别从上一行、上一列进行转移,然后取最大值并且加上到的那个点的值,如果算重了就减去,最后输出就行。下边说一下具体的状态:

定义\(f[i][j][k][l]\)为一条路径到\(i\)\(j\)列,另一条到\(k\)\(l\)列得到的最大值,状态转移如下:

\[f[i][j][k][l] = max(max(f[i-1][j][k-1][l],f[i-1][j][k][l-1]),max(f[i][j-1][k-1][l],f[i][j-1][k][l-1]))+a[i][j]+a[k][l]; \]

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zygwzp.html