高度由习惯堆积

BZOJ2726 SDOI2012 任务安排

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

BZOJ2738 矩阵乘法

题目给你一个N*N的矩阵,不用算矩阵乘法,但是每次询问一个子矩形的第K小数。思路整体二分。整体二分主要适用于对于二分状态的改变,可以在可接受的复杂度内修改的题目。就本题而言,二分答案,如果考虑将[1,mid]的区间内的点加入树状数组中,在二维平面上标记为1,然后比较每个询问与K的关系,接着将询问分组,接着二分。以上应该是整体二分的基本模型。代码#include<bits/stdc++....

BZOJ 4553 [Tjoi2016&Heoi2016]序列

题目佳媛姐姐过生日的时候,她的小伙伴从某宝上买了一个有趣的玩具送给他。玩具上有一个数列,数列中某些项的值可能会变化,但同一个时刻最多只有一个值发生变化。现在佳媛姐姐已经研究出了所有变化的可能性,她想请教你,能否选出一个子序列,使得在任意一种变化中,这个子序列都是不降的?请你告诉她这个子序列的最长长度即可。注意:每种变化最多只有一个值发生变化。在样例输入1中,所有的变化是1 2 32 2 31...
July 21, 2019

BZOJ1766 Photo

PDF题目平面上有若干个点,现在要求用最少的底边在X轴上且面积小等A的矩形覆盖所有点,这些矩形可以重叠。 N<=100,A<=2000000思路一开始想的是简单的区间dp。$f[l,r]$表示覆盖完$[l,r]$一段区间的所有点的最小矩形数,然后很快就发现了不对之处:对于图中所示情况,单纯考虑区间之间的分割是行不通的,也就是说,对于相互重叠的矩形,高度那一维也很有必要记录。重新定...