【题解】USACO 2020Feb Gold Help Yourself

先放结论

首先把线段按左端点升序排序

我们设 sumisum_i 为坐标小于等于i的右端点个数

dpidp_i 为考虑到第 ii 条线段时的答案

则递推式为 dpi=2dpi1+2sumli1dp_i=2dp_{i-1}+2^{sum_{l_i-1}}

阅读全文 »