洛谷 错题本
P1004 [NOIP 2000 提高组] 方格取数
#走两次dp
如果只走一次,这题是非常经典的DP。但是要走两次,就变得非常有难度。
首先,可以简单地推广:要走两次,dp就存四个下标:
int[][][][] dp = new int[N][N][N][N]; |
我们只需要遍历所有可能,并且比较四种走法(同下、同右、一下一右),取最大值就可以了。
注意,一个数只能取一次,需要一个判断防止重复取数。
for (int i1 = 1; i1 < N; i1 += 1) { |
当然,4个循环时间复杂度太高了。我们可以用一个k == i1 + j1 == i2 + j2
来减少一重循环。
这个k利用得很巧妙,因为每次要么向下走,要么向右走,所以k-1 == i-1 + j == i + j-1
,全程使用k-1
就能代表所有情况。