24年在洛谷刷刷题,遇到过一个双人路径问题,P1004 [NOIP 2000 提高组] 方格取数
,题解的4维数组对于博主这样一个菜鸟,实在难以理解,于是就搁置了。然而25年的时候又遇到了P1006 [NOIP 2008 提高组] 传纸条
这样一个题目,于是死去的记忆突然开始攻击我。结合题解,尝试自己画了几张图帮助理解,也分享在博客里。
假设两个人同时从1,1
位置出发,第一个人用绿点表示,第二个人用红点表示,可以发现,两个人走同样多的步数之后,他们的落点必然会在一条45度的斜线上。这条斜线上的x,y坐标之和始终是相同的。将这个和用变量k来表示的话,两人走出第一步时,k等于3,走出第二步时,k=4,以此类推。
而因为该斜线上的点,单独对比x坐标(或y坐标)均不相同,所以我们可以用一个三维数组来同时表示两个点,比如上图中间的部分,第三步时k值为5,第一个绿点x坐标为4,第二个红点x坐标为3,两个点的位置可以表示为:
5,4,3
而想要到达[k][i][i]
,可能会有以下4种途径:
两条路径都从左方移动过来:[k-1][i-1][j-1]
;
两条路径都从上方移动过来:[k-1][i][j]
;
第一条路径从上方,第二条路径从左方移动过来:[k-1][i][j-1]
;
第一条路径从左方,第二条路径从上方移动过来:[k-1][i-1][j]
。