做法疑问
查看原帖
做法疑问
1093247
s1mp1ng楼主2024/12/1 20:01

挪指针的操作 1 显然转移,那我 dpi,jdp_{i,j} 表示 aa 走到 iibb 走到 jj 的花费是不是如果更新值一定是 dp,jdp_{*,j} 其中 * 是求的最前面的位置,但是方案是在 [,i1][*,i-1] 中转移的。

dpi,jdp_{i,j} 在固定 jj 的时候是不是单调不减的?可以理解为一个更大的 ii' 可以通过放弃某些删除来变成一个更小的 ii 吗?如果单调不减是不是可以去 [,i][*,i] 里二分找一段等于 dp,jdp_{*,j} 的 dp 值然后把它们的方案转移?

2024/12/1 20:01
加载中...