夢に僕らで帆を張って
来るべき日のために夜を超え

标签 单调队列 下的文章

October 18, 2019

洛谷P3572/POI2014 PTA-Little Bird

题意从$1$开始,跳到比当前矮的不消耗体力,否则消耗$1$点体力,每次询问有一个步伐限制,求每次最少耗费多少体力数据范围:$2 \le n \le 1000000$题解用$f[i]$表示前$i$个的步数,易得状态转移方程$$ f[i]=\min_{j=i-k}^{i-1}\left\{ \begin{aligned} &f[j] &a[j] > a[i]...
October 18, 2019

洛谷P3594/POI2015 WIL-Wilcze doły

题意给定一个长度为$n$的序列,你有一次机会选中一段连续的长度不超过$d$的区间,将里面所有数字全部修改为$0$。请找到最长的一段连续区间,使得该区间内所有数字之和不超过$p$数据范围:$1 \le d \le n \le 2000000,0 \le p \le 10^{16}$题解首先能够想到枚举区间左右端点$l,r$,再减去区间内和最大的一段,用前缀和表示为$$s[r]-s[l-1]-\...
October 16, 2019

洛谷P1776 宝物筛选

题意多重背包数据范围:$0 \le w \le 4 \cdot 10^4,1 \le n \le 100$题解设$w$为价值,$v$为体积,$c$为数量多重背包的状态转移方程为$$f[i][j]=\max(f[i-1][j-kv]+kw)$$其中$k \in [1,c]$由于$i$一定从$i-1$转移而来,所以第一维可以去掉$$f[j]=\max(f[j-kv]+kw)$$但是这样$dp$的...
October 16, 2019

洛谷P2569/SCOI2010 股票交易

题意略数据范围:$0 \le w,t \le 2000,1 \le p \le 2000,1 \le bp_i \le ap_i \le 1000,1 \le as_i,bs_i \le p$题解算法:动态规划用$f[i][j]$表示第$i$天持有$j$股股票,前$i$天的最大收益首先,若从第$i$天开始买股票,有$$f[i][j]=-ap_i \cdot j$$其中$j \in [0,as...
September 28, 2019

洛谷P3084/USACO13OPEN 照片Photo

题意有$n$头奶牛,$m$条约束$(a_i,b_i)$,表示$a_i$到$b_i$间有且仅有一头带斑点的奶牛,求最多可能有多少只斑点奶牛数据范围:$1 \le n \le 200000,1 \le m \le 100000$题解将有且仅有一头拆解为至多一头+至少一头初步思路为差分约束,但明显复杂度过高发现可以$dp$,用$f[i]$表示第$i$头奶牛有斑点的情况下前$i$头奶牛最多有多少斑点...
September 26, 2019

洛谷P2627 修剪草坪

题意从数列$a$中选出若干数,但不能有超过$k$个连续的数字被选择,求选出数字的最大和数据范围:$1 \le n \le 10^5,1 \le a_i \le 10^9$题解用$f[i]$表示选到第$i$个时的最大值,显然,在$j \in [i-k,i]$一定存在至少$1$个断点,否则存在超过$k$的连续段,所以枚举该断点$$f[i]=max(f[j-1]+a[j+1]+ \dots +a[...