51NOD1084
fightinggg
8月 05, 2019
转移自老blog
(2 <= M, N <= 200)
(1 <= A[i,j] <= 10000)
转移方程很好写，看似n^4个状态，但是能够注意到i+j=k+l才是合法状态，于是状态变为n^3
51NOD1084
链接
题意
一个M*N矩阵中有不同的正整数，经过这个格子，就能获得相应价值的奖励，先从左上走到右下，再从右下走到左上。第1遍时只能向下和向右走，第2遍时只能向上和向左走。两次如果经过同一个格子，则该格子的奖励只计算一次，求能够获得的最大价值。(2 <= M, N <= 200)
(1 <= A[i,j] <= 10000)
题解
将两条路都看做从左上角出发，dp[i][j][k][l]代表第一次走到(i,j)第二次走到（k,l）的最大价值，转移方程很好写，看似n^4个状态，但是能够注意到i+j=k+l才是合法状态，于是状态变为n^3