DPtrick : 延迟钦定 / 贡献延后计算

· · 算法·理论

首先我很菜，这东西只是给自己用的，见得少，难免以偏概全，错别字也请包容

这个东西的实质就是说当做一个dp的问题的时候，如果有的贡献不能在当下立刻计算，而是需要在未来某一个时间计算时就可以使用这个trick

或者形如min(下标，值)的形式也是可以使用这个技巧的，但是需要先将值（这里指值和下标扔到一起）排序。

排序的意义在于让贡献可以被延后计算而不是完全没有办法计算，这个是在Min处取到贡献，那么就应该让值从小到大去扫描。

上文这个还要结合另一个trick：将排列的匹配转化为二分图的匹配

dp状态设计的时候自然需要多一维度维护有几个点是钦定在未来计算（和某一个特定值有一定大小关系）

例题：P14364,AT_arc207_a,QOJ2573