高度由习惯堆积
August 14, 2019

ZJOI2011 营救皮卡丘

题目题目链接思路首先,看数据范围比较小,想到网络流。对于最短路的那部分,在走到$j$的时候,不能经过$>j$的点,所以在$Floyd$的时候我们加一层限制$K<=j$处理出最短路。然后考虑网络流建边。会发现有这么几个限制:从小的点走向大的点每个点都必须走到不得超过$K$条路径因为每一条路径一定都是从较小的点走向较大的点的,所以其实这是一个$DAG$。然后考虑如何在建图中体现这些性...

NOI2009 诗人小G

题目小G是一个出色的诗人,经常作诗自娱自乐。但是,他一直被一件事情所困扰,那就是诗的排版问题。一首诗包含了若干个句子,对于一些连续的短句,可以将它们用空格隔开并放在一行中,注意一行中可以放的句子数目是没有限制的。小G给每首诗定义了一个行标准长度(行的长度为一行中符号的总个数),他希望排版后每行的长度都和行标准长度相差不远。显然排版时,不应改变原有的句子顺序,并且小G不允许把一个句子分在两行或...

BZOJ2726 SDOI2012 任务安排

题目机器上有N个需要处理的任务,它们构成了一个序列。这些任务被标号为1到N,因此序列的排列为1,2,3...N。这N个任务被分成若干批,每批包含相邻的若干任务。从时刻0开始,这些任务被分批加工,第i个任务单独完成所需的时间是Ti。在每批任务开始前,机器需要启动时间S,而完成这批任务所需的时间是各个任务需要时间的总和。注意,同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系...