心理问题求助
  • 板块灌水区
  • 楼主Amoribus
  • 当前回复9
  • 已保存回复9
  • 发布时间2024/9/14 18:22
  • 上次更新2024/9/16 09:40:12
查看原帖
心理问题求助
935976
Amoribus楼主2024/9/14 18:22

我一直理解不了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+1dp_{x,y,c,la,lb}=\sum_{ca=0}^{la} \sum_{cb=0}^{lb}dp_{x-1,y,c-a_{x,y}-b_{x,y},la-ca+1,lb-cb}+dp_{x,y-1,c-a_{x,y}-b_{x,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−1dp_{x,y,c,la,lb}=dp_{x,y,c-a_{x,y},la-1,lb}+dp_{x,y,c-b_{x,y},la,lb-1}-dp_{x,y,c-a_{x,y}-b_{x,y},la-1,lb-1} 再加上 dpx−1,y,c,la+1,lb+dpx,y−1,c,la,lb+1dp_{x-1,y,c,la+1,lb}+dp_{x,y-1,c,la,lb+1}

1.为什么可以这样做,dp二维前缀和的思路是什么?和直接的二维前缀和有什么相通之处?

2.如果可以的话,给我讲讲这道题的思路是什么,转移方程的优化是怎么得出的。

2024/9/14 18:22
加载中...