P1004 [NOIP2000 提高组] 方格取数 题解

发布时间 2023-12-03 20:48:32作者: ShawyYum

题意:

思路:

考虑四维 $ 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] $