p1006没人讲过的如何实现的去重
  • 板块学术版
  • 楼主JiuZhE66666
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/8/16 10:27
  • 上次更新2023/11/3 03:27:11
查看原帖
p1006没人讲过的如何实现的去重
1049051
JiuZhE66666楼主2023/8/16 10:27

也是看了题解后才有的思路,但是大佬们好像没有讲怎么实现的去重(也可能是太容易想了?)

设人A坐标为(i,j),人B坐标为(k,l)

设四维数组f[i][j][k][l]表示当A走到(i,j)点,B走到(k,l)点时,两个人走过的所有路程和中最大的那个和。

因为A,B可以往右走,也可以往下走,所以f[i][j][k][l]是从2x2=4个地方中的最大的一个走过来的,即f[i][j][k][l]=max(max(f[i-1][j][k-1][l],f[i][j-1][k][l-1]),max(f[i][j-1][k-1][l],f[i-1][j][k][l-1]

两人的步数是同步的,若两人的坐标相同,那么对应的f不会赋值,而对每一个有值的f而言,一定是由若干个同样有值的f走过来的。所以每一个有值的f对应的两人路线一定是不会重复的。如此扩散,最后的结果(两人走的路线)也一定是不会重复的。

2023/8/16 10:27
加载中...