我一直理解不了dp的二维前缀和优化,可以讲讲它的思想是什么样的吗?(想了好几天都没想明白,很烦躁,甚至想过一些很不好的事情)
比如 P9743 「KDOI-06-J」旅行 的题解,
其中,dpx,y,c,la,lb=∑ca=0la∑cb=0lbdpx−1,y,c−ax,y−bx,y,la−ca+1,lb−cb+dpx,y−1,c−ax,y−bx,y,la−ca,lb−cb+1
可以改写为 dpx,y,c,la,lb=dpx,y,c−ax,y,la−1,lb+dpx,y,c−bx,y,la,lb−1−dpx,y,c−ax,y−bx,y,la−1,lb−1
再加上 dpx−1,y,c,la+1,lb+dpx,y−1,c,la,lb+1
1.为什么可以这样做,dp二维前缀和的思路是什么?和直接的二维前缀和有什么相通之处?
2.如果可以的话,给我讲讲这道题的思路是什么,转移方程的优化是怎么得出的。