社区讨论

心理问题求助

P9743「KDOI-06-J」旅行参与者 5已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@m12039ll
此快照首次捕获于
2024/09/14 18:24
去年
此快照最后确认于
2025/11/04 21:15
4 个月前
查看原帖
我一直理解不了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.如果可以的话,给我讲讲这道题的思路是什么,转移方程的优化是怎么得出的。

回复

6 条回复,欢迎继续交流。

正在加载回复...