「SCOI2010」股票交易-dp+单调队列

lxhgww预测到了未来 $T$ 天内某只股票的走势,第 $i$ 天的股票买入价为每股 $AP_i$ ,第 $i$ 天的股票卖出价为每股 $BP_i$ (数据保证对于每个 $i$ ,都有$AP_i \ge BP_i$ ),第$i$ 天的一次买入至多只能购买 $AS_i$ 股,一次卖出至多只能卖出 $BS_i$ 股。两次交易(某一天的买入或者卖出均算是一次交易)之间,至少要间隔 $W$ 天;在任何时间一个人的手里的股票数不能超过 $MaxP$ 。

在第 $1$ 天之前,lxhgww手里有数目无限的钱,但是没有任何股票,在 $T$ 天以后, lxhgww 能赚到的钱最多是多少?

「POI2014」PTA-单调队列

给定 $n$ 个点的高度,规定从 $1$ 点出发,跳到比高度小于当前点的点不消耗体力,否则消耗一点体力,最后到达 $n$ 点。

$q$ 次询问,每次询问有一个步伐限制 $k$ ,求最少耗费的体力。

「SDOI2011」消防-树的直径+单调队列

某个国家有$n$个城市,这$n$个点之间的边构成一棵树。

现求一条边长度和不超过$S$的路径(两端都是城市,可以只为一个城市),使得所有城市到这条路径的距离的最大值最小,并输出这个最小值。

「HAOI2007」理想的正方形-单调队列

有一个 $a \times b$ 的整数组成的矩阵,现请你从中找出一个 $n\times n$ 的正方形区域,使得该区域所有数中的最大值和最小值的差最小,输出这个最小的差值。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×