高度由习惯堆积

分类 算法:贪心 下的文章

LOJ2710 election

题目有一个长度为$N$的字符串$S[1…N]$,它仅由C和T两种字母组成。现在有$Q$个查询,每个查询包含两个整数$L$和$R$,表示:设新字符串 $S'=S[L…R]$,至少在$S'$中要删除多少个字符,才能保证:对于$S'$的每一个前缀与每一个后缀,其C的数量都不小于T的数量。思路28pts有一个显然的贪心,对于一段区间,先扫描前缀,遇到不合法的点就删掉,再扫描后缀,把不合法的点删掉,这...

NOIP2012 疫情控制

题目H 国有 n 个城市,这 n 个城市用 n-1 条双向道路相互连通构成一棵树,1 号城市是首都, 也是树中的根节点。H 国的首都爆发了一种危害性极高的传染病。当局为了控制疫情,不让疫情扩散到边境 城市(叶子节点所表示的城市),决定动用军队在一些城市建立检查点,使得从首都到边境 城市的每一条路径上都至少有一个检查点,边境城市也可以建立检查点。但特别要注意的是, 首都是不能建立检查点的。现在...
February 17, 2019

IOI2004 假期

题目Lay博士正在制定下个假期去C市的游玩计划。在C市共有nn个城市,它们全部位于一条高速公路上。这些城市连续地编号为$0$到$n−1$。对于城市$i(0<i<n−1)$而言,与其相邻的城市是$i−1$和$i+1$。但是对于城市00,唯一与其相邻的是城市$1$。而对于城市$n−1$,唯一与其相邻的是城市$n−2$。城市$i$有$a_i$和景点。Lay博士有$d$天假期并且打算要参...
February 17, 2019

BZOJ1999 树网的核(数据加强版)

题目设T=(V, E, W) 是一个无圈且连通的无向图(也称为无根树),每条边带有正整数的权,我们称T为树网(treenetwork),其中V, E分别表示结点与边的集合,W表示各边长度的集合,并设T有n个结点。 路径:树网中任何两结点a,b都存在唯一的一条简单路径,用d(a,b)表示以a,b为端点的路径的长度,它是该路径上各边长度之和。我们称d(a,b)为a,b两结点间的距离。 一点v到一...
February 17, 2019

51nod1288 汽油补给

贪心日常不会做题目有(N+1)个城市,0是起点N是终点,开车从0 -> 1 - > 2...... -> N,车每走1个单位距离消耗1个单位的汽油,油箱的容量是T。给出每个城市到下一个城市的距离D,以及当地的油价P,求走完整个旅途最少的花费。如果无法从起点到达终点输出-1。例如D = {10, 9, 8}, P = {2, 1, 3},T = 15,最小花费为41,在0加上...