zcmimi's blog

arrow_back决策单调性共6篇文章

avatar
zc
2020-01-21 10:36:00
查看原题

点击跳转

设当前区间为[l,r]

res=\sum_{i=l}^r p_i\times[\prod_{j=l,j!=i}^r(1-p_j)]

s_{[l,r]}表示\prod_{i=l}^r(1-p_i)

res=s_{[l,r]}\sum_{i=l}^r \frac{p_i}{1-p_i}

a_i=1-p_i,b_i=\frac{p_i}{1-p_i}

res=\prod_{i=l}^ra_i\sum_{i=l}^rb_i

假设现在区间变成了[l,r+1]

A=\prod_{i=l}^ra_i,B=\sum_{i=l}^rb_i

res'=A\times a_{r+1}(B+b_{r+1})

=A(a_{r+1}B+a_{r+1}b_{r+1})

=A(a_{r+1}B+p_{r+1})

res'>res,那么a_{r+1}B+p_{r+1}>B

1-p_{r+1}+\frac{p_{r+1}}B>1

\therefore B<1

那么对于每个l,只需要找到最远的r使\sum_{i=l}^rb_i<1

而这又具有单调性,那么\mathcal{O(n)}就可以解决了

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

f_i为前i个最小代价

s_i为前i个字符串总字符数

f_i=\min(f_j+|(s_i-s_j)+(i-j-1)-L|^p)

可以发现这个方程有决策单调性

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

题目大意:

给定一个长度为 n\leq 500000 的序列 a_1, a_2, \cdots, a_n ,要求对于每一个 1 \leq r \leq n ,找到最小的非负整数 f_{r} 满足

\forall l\in\left[1,n\right]:a_l \leq a_r + f_{r} - \sqrt{|r-l|}

解法

考虑l<r,r>l的将序列翻转后再来一次就可以了

f_r= \max(a_l+\sqrt{r-l})-a_r(l\in[1,r])

可以证明f_r的最优决策点是递增的

可以打表

分治解法

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

f_i表示[1,i]最多变成多少个

f_i=\max_{s_i=s_j}(f[j-1]+s_j\times (\sum_{i=j}^i[s_i=s_j])^2)

我们可以发现如果s_j=s_{j'}(j'< j),从j'转移一定比从j

这一条件满足决策单调性!

我们可以用单调队列维护单调性

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

f(i,j)表示前i个划分成j段最少的费用

我们设calc(l,r)表示[l,r]划分成一段的费用

f(i,j)=\min_{x=1}^i(f(x-1,j-1)+calc(x,i))

可以发现这个dp方程具有决策单调性

i<i',那么k_i\le k_{i'}(决策点)

把连续一段拆成两边更优x^2+y^2\le (x+y)^2(x,y\ge 0)

更巧的是w(l,r)可以用类似莫队的方法线性转移

这里采用分治的方法实现

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

题目大意:

给定一个长度为 n\leq 500000 的序列 a_1, a_2, \cdots, a_n ,要求对于每一个 1 \leq r \leq n ,找到最小的非负整数 f_{r} 满足

\forall l\in\left[1,n\right]:a_l \leq a_r + f_{r} - \sqrt{|r-l|}

解法

考虑l<r,r>l的将序列翻转后再来一次就可以了

f_r= \max(a_l+\sqrt{r-l})-a_r(l\in[1,r])

可以证明f_r的最优决策点是递增的

可以打表

分治解法

1/1
Search
search