1672: [Usaco2005 Dec]Cleaning Shifts 清理牛棚

考虑令f[i]表示至少把前i个点打扫了所需要的最小花费,

那么对于第i个奶牛打扫的即为f[a[i].e] = min(f[a[i].s-1]+a[i].w);

考虑更新了f[a[i].e]实际上也对于前a[i].e个点均有影响,所以还需对f[j]取min j < a[i].e

知道树状数组是可以维护前缀最小值的,那么反转区间,随便维护即可。

c++代码如下:

 

5 + 8 =