标签归档:单调栈

[bzoj1597][Usaco2008 Mar]土地购买

简单题,为了练习CHT所以来写一下。。结果发现写错了一个地方导致没1AQQ图片20160623113044

这种题N辣么小,肯定是想dp的对吧,但是我们发现并不能连续的做,那么怎么办呢?

我们发现,对于两个土地i,j,如果满足a[i]\geq a[j],b[i]\geq b[j],那么在买i的时候永远可以带上j

继续阅读

[BZOJ3482][COCI2013]hiperprostor

Orz Claris菊苣

对于这道题我们发现q很小,那么大概率是让你在线去做

然后我们知道n,m也很小,大概率是用n,m做一个dp

所以设f[i][j]表示从s出发,到达i,恰好经过jx边的最短路,利用spfa求出。

如果对于任意的i都有f[t][i]=\infty,则答案为无解。

继续阅读

[BOI2012] balls

题目大意

给你n个球和n个洞,第i个球对应第i个洞,洞i里如果获得一个球则加c_i分,你现在有一个挡板,可以向左也可以向右,可以任意长度。该挡板能将一段区间内的球下落在挡板左侧/右侧的洞里,问分数最大是多少(对于向左向右两种情况分别输出)。

继续阅读

[bzoj 1012][JSOI2008] 最大数

Description

  现在请求你维护一个数列,要求提供以下两种操作:1、 查询操作。语法:Q L 功能:查询当前数列中末尾L个数中的最大的数,并输出这个数的值。限制:L不超过当前数列的长度。2、 插入操作。语法:A n 功能:将n加上t,其中t是最近一次查询操作的答案(如果还未执行过查询操作,则t=0),并将所得结果对一个固定的常数D取模,将所得答案插入到数列的末尾。限制:n是非负整数并且在长整范围内。注意:初始时数列是空的,没有一个数。

继续阅读