标签归档:Convex hull trick

[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分,你现在有一个挡板,可以向左也可以向右,可以任意长度。该挡板能将一段区间内的球下落在挡板左侧/右侧的洞里,问分数最大是多少(对于向左向右两种情况分别输出)。

继续阅读