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

我一直理解不了dp的二维前缀和优化,可以讲讲它的思想是什么样的吗?(想了好几天都没想明白,很烦躁,甚至想过一些很不好的事情)

比如 P9743 「KDOI-06-J」旅行 的题解,

其中,dpx,y,c,la,lb=ca=0lacb=0lbdpx1,y,cax,ybx,y,laca+1,lbcb+dpx,y1,cax,ybx,y,laca,lbcb+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,cax,y,la1,lb+dpx,y,cbx,y,la,lb1dpx,y,cax,ybx,y,la1,lb1dp_{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} 再加上 dpx1,y,c,la+1,lb+dpx,y1,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
加载中...