社区讨论

此题的大部分题解对状态转移方程的理解存在问题

P3147[USACO16OPEN] 262144 P参与者 3已保存回复 9

讨论操作

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

当前回复
9 条
当前快照
1 份
快照标识符
@mi7k4rhz
此快照首次捕获于
2025/11/20 22:59
3 个月前
此快照最后确认于
2025/11/21 11:51
3 个月前
查看原帖
从去年初见这道题的题解我就有了这个想法,只是碍于实力不足无法解释故只能死记,大部分题解认为 dpi,jdp_{i,j} 表示以 ii 为左端点能合成出 jj 的右端点位置,状态转移方程为 dpi,j=dpdpi,j1,j1dp_{i,j}=dp_{dp_{i,j-1},j-1},然而初始化 dpi,ai=i+1dp_{i,a_{i}}=i+1 就有点无法解释了,为什么还没合成右端点就是 i+1i+1 呢?又比如状态转移方程本身,先是从 ii 合成出 j1j-1 ,此时 dpi,j1dp_{i,j-1} 这里的数字已经被用来合成了,为何又从 dpi,j1dp_{i,j-1} 开始合成即 dpdpi,j1,j1dp_{dp_{i,j-1},j-1} 呢?所以我认为,对于这个状态转移方程真正的定义是应为 dpi,jdp_{i,j} 表示ii 为左端点能合成出 jj 的右端点的下一个位置,这才能合理解释所有。

回复

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

正在加载回复...