介绍
消除后效性,狭义上指的是dp,但广义上来说,贪心做法等也有时需要考虑后效性问题。
总体而言,只要你是想要把一个问题拆开来分析求解,那么合起来的时候,就要考虑后效性了。
案例分析
CF-1024-D. Quartet Swapping(四重交换) 这个是解决了交换数量要保持相同,但是最优情况可能无法保持相同,如何找到次优情况呢?或者说什么发现该情况只适用于次优情况呢?涉及冒泡排序以及逆序对。
2025金马高校联赛-B战术单元协同训练 利用链表来消除后效性
Edu-179-E. Changing the String 在线处理比较难,需要考虑对后续操作的影响,可以采用离线方法处理,因为下标小的。