51NOD1084

转移自老blog

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