题意:
思路:
考虑四维 $ dp $ :
设 $ dp[i][j][k][l] $ 表示两条路径分别走到 $ (i,j) $ 和 $ (k,l) $ 时所能获取的最大和,显然会超时。
考虑三维 $ dp $ :
设 $ dp[i][j][k] $ 表示两条路径走了 $ i $ 步分别走到第 $ j $ 行和第 $ k $ 行时所能获取的最大和,通过当前步数 $ i $ 以及当前行数 $ j $ 和 $ k $ ,可以得出两条路径分别走到第 $ i + 2 - j $ 列和第 $ i + 2 - k $ 列,那么状态转移方程有:
$ dp[i][j][k] = max(dp[i - 1][j][k],dp[i - 1][j - 1][k],dp[i - 1][j][k - 1],dp[i - 1][j - 1][k - 1]) + a[j][i + 2 - j] + a[k][i + 2 - k] $
当且仅当 $ j = k $ 时,两条路径走到同一点,由于不能重复取值,那么状态转移方程有:
$ dp[i][j][k] = dp[i][j][k] - a[j][i + 2 - j] $ 或 $ dp[i][j][k] = dp[i][j][k] - a[k][i + 2 - k] $
标签:NOIP2000,题解,P1004,路径,两条,dp From: https://www.cnblogs.com/ShawyYum/p/17873731.html