Tag: 贪心

7 篇文章

bzoj 2006. [NOI2010]超级钢琴 题解
Description 题目链接 给定一个长度为 $n$ 的序列,选出 $k$ 个长度在 $[L,R]$ 之间的子段(不可重复),求 $k$ 个子段和的最大值。 $N\leq 500,000,k\leq 500,000,-1000\leq A_i \leq 1000,1\leq L\leq R\leq N$ Solution 由于 $n$ 十分巨大…
Luogu P1514 引水入城 题解
题目链接 Describe 在一个遥远的国度,一侧是风景秀美的湖泊,另一侧则是漫无边际的沙漠。该国的行政区划十分特殊,刚好构成一个$N$行$\times M$列的矩形,如上图所示,其中每个格子都代表一座城市,每座城市都有一个海拔高度。 为了使居民们都尽可能饮用到清澈的湖水,现在要在某些城市建造水利设施。水利设施有两种,分别为蓄水厂和输水站。蓄水厂的…
Luogu P1084 疫情控制 题解
Link Luogu Problem view Describe 有一棵以$1$为根节点的树,现在要在除根节点外的点设立阻拦,使得没有一条路径可以从根节点到任意一个叶子节点。这些阻拦需要$m$个军队来设立,这$m$个军队中第$i$个一开始在点$q_i$上,军队移动的时间等于移动经过的边权之和,问最少要多少时间才能设立完阻拦。注意:不同的军队可以同时…