博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[USACO2005][POJ3171]Cleaning Shifts(DP+线段树优化)
阅读量:4344 次
发布时间:2019-06-07

本文共 415 字,大约阅读时间需要 1 分钟。

题目:

题意:给你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

转载于:https://www.cnblogs.com/wmrv587/p/3692783.html

你可能感兴趣的文章
阶段3 2.Spring_09.JdbcTemplate的基本使用_5 JdbcTemplate在spring的ioc中使用
查看>>
阶段3 3.SpringMVC·_07.SSM整合案例_02.ssm整合之搭建环境
查看>>
小D课堂 - 零基础入门SpringBoot2.X到实战_第1节零基础快速入门SpringBoot2.0_3、快速创建SpringBoot应用之手工创建web应用...
查看>>
小D课堂 - 零基础入门SpringBoot2.X到实战_第1节零基础快速入门SpringBoot2.0_5、SpringBoot2.x的依赖默认Maven版本...
查看>>
阶段3 3.SpringMVC·_07.SSM整合案例_08.ssm整合之Spring整合MyBatis框架
查看>>
小D课堂 - 零基础入门SpringBoot2.X到实战_第2节 SpringBoot接口Http协议开发实战_9、SpringBoot基础HTTP其他提交方法请求实战...
查看>>
小D课堂 - 零基础入门SpringBoot2.X到实战_第2节 SpringBoot接口Http协议开发实战_12、SpringBoot2.x文件上传实战...
查看>>
小D课堂 - 零基础入门SpringBoot2.X到实战_第4节 Springboot2.0单元测试进阶实战和自定义异常处理_19、SpringBoot个性化启动banner设置debug日志...
查看>>
小D课堂 - 零基础入门SpringBoot2.X到实战_第4节 Springboot2.0单元测试进阶实战和自定义异常处理_20、SpringBoot2.x配置全局异常实战...
查看>>
小D课堂 - 零基础入门SpringBoot2.X到实战_第5节 SpringBoot部署war项目到tomcat9和启动原理讲解_23、SpringBoot2.x启动原理概述...
查看>>
小D课堂 - 零基础入门SpringBoot2.X到实战_第4节 Springboot2.0单元测试进阶实战和自定义异常处理_21、SpringBoot2.x配置全局异常返回自定义页面...
查看>>
小D课堂 - 零基础入门SpringBoot2.X到实战_第8节 数据库操作之整合Mybaties和事务讲解_32..SpringBoot2.x持久化数据方式介绍...
查看>>
小D课堂 - 零基础入门SpringBoot2.X到实战_第8节 数据库操作之整合Mybaties和事务讲解_34、SpringBoot整合Mybatis实操和打印SQL语句...
查看>>
小D课堂 - 零基础入门SpringBoot2.X到实战_第8节 数据库操作之整合Mybaties和事务讲解_35、事务介绍和常见的隔离级别,传播行为...
查看>>
小D课堂 - 零基础入门SpringBoot2.X到实战_第9节 SpringBoot2.x整合Redis实战_40、Redis工具类封装讲解和实战...
查看>>
小D课堂 - 零基础入门SpringBoot2.X到实战_第9节 SpringBoot2.x整合Redis实战_37、分布式缓存Redis介绍...
查看>>
小D课堂 - 零基础入门SpringBoot2.X到实战_第10节 SpringBoot整合定时任务和异步任务处理_42、SpringBoot常用定时任务配置实战...
查看>>
小D课堂 - 零基础入门SpringBoot2.X到实战_第9节 SpringBoot2.x整合Redis实战_39、SpringBoot2.x整合redis实战讲解...
查看>>
小D课堂 - 零基础入门SpringBoot2.X到实战_第14节 高级篇幅之SpringBoot多环境配置_59、SpringBoot多环境配置介绍和项目实战...
查看>>
小D课堂 - 零基础入门SpringBoot2.X到实战_第10节 SpringBoot整合定时任务和异步任务处理_41、SpringBoot定时任务schedule讲解...
查看>>