[USACO2005][POJ3171]Cleaning Shifts(DP+线段树优化)

题目:http://poj.org/problem?id=3171

题意:给你n个区间[a,b],每个区间都有一个费用c,要你用最小的费用覆盖区间[M,E]

分析:经典的区间覆盖问题,百度可以搜到这个专题。

线段覆盖问题一般考虑贪心和DP,但是每个区间又有了一个费用c,本渣觉得贪心貌似不太行(不知道神犇门有木有贪心解法),然后便考虑DP

设f[i]表示覆盖[M,i]的最小总费用

那么有f[t[i].a]=min(f[j]+t[i].c) t[i].a-1<=j<=t[i].b-1

那么ans=f[E]

不过这个是n^2,无法承受

观察到取min(f[j]),且j的取值范围只与i有关(不像与前面j有关的一类单调队列优化dp问题),所以考虑用线段树优化。即每次先询问[t[i].a-1,t[i].b-1]区间的f[]最小值,然后再把新的f[t[i].a]加入线段树

时间效率nlogn

上一篇:linux下一个oracle11G DG建立(一个):准备环境


下一篇:Linux下MySQL的简单操作