zcmimi's blog

arrow_back动态规划共95篇文章

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

点击跳转

f_i为前i个任务的费用,t_i为前i个任务时间的总和,w_i为前i个任务费用的总和

f_i=\min_{j=0}^{i-1}(f_j+s\times(w_n-w_j)+t_i\times(w_i-w_j))

设任意0\le j<k<ij转移比从k转移优,那么

f_j+s\times(w_n-w_j)+t_i\times(w_i-w_j) \le f_k+s\times(w_n-w_k)+t_i\times(w_i-w_k) \\ t_i(w_k-w_j)\le f_k-f_j+s(w_j-w_k) \\ t_i\le \frac{f_k-f_j+s(w_j-w_k)}{w_k-w_j}

维护了个下凸壳交了上去,结果听取\color{red}\text{WA}声一片

仔细看了看|T_i|\le 2^8

这也就意味着我们每次截取的直线的斜率不再单调递增,单调队列不能再满足需要

为了保证决策状态的有序性,我们还是选择用一个单调栈维护下凸包。

因为决策集合已经有序,对于任意直线,我们只用在队列中二分出使截距最小的交点

由于出题人十分毒瘤,我们要把斜率大小的判断从相除改成十字相乘

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

点击跳转

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

点击跳转

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 = f_j + [ a_i \le a_j ] (i < j \le n)

题目要求是复杂度O(nq)

一看有个步伐限制

那么显然加个单调队列就完事了

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

点击跳转

f[st][sta]表示起点是st,当前节点是否访问过的状态二进制下是sta

顺便记录d[st][sta]表示f[st][sta]最小时每个节点距离st的距离

我们可以用填表法向前推进

f[st][sta'] = \min(f[st][sta'],f[st][sta]+(d[st][sta][x]+1)\times L) (sta' = sta | 2^{to-1})

最坏情况下复杂度: \Theta(n \times 2^n \times n^2)

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

点击跳转

首先二分出最大一段的最小值,然后dp找出方案数

f[i][j]表示前j个分成i组的方案数,求出的最小值为x

f[i][j] = \sum(f[i-1][k])(S_j-S_k \le x,k \le j-1)

\Theta(n^3m)当然会TLE

我们发现只要找到最小的k之后[k,j-1]都是合法的

这时我们就可以前缀和优化dp

sum[i][j] = \sum_{k=0}^j f[i][k]

f[i][j]=sum[i-1][j-1] - sum[i-1][k-1]

可是\Theta(n^2m)还是TLE

我们可以先预处理出第一个S_j-S_k \le xk

因为S_i具有单调性,所以k不需要每次都重新枚举

还没结束

因为f[i][j]每次更新的时候只需要用到f[i-1][...]这一维,我们可以用滚动数组滚掉数组的一维

但是\Theta(nm+n \log \sum L_i)的复杂度还是觉得很悬

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

点击跳转

第一问:

数列中肯定有些是合法的,有些是不合法的

如果a_i-a_j < j-i就无法同时保留两者

那么a_i-a_j \ge j-i

所以a_i-i < a_j-j

b_i = a_i -i

b的最长不下降子序列长度就是最多能保留个数

第二问:

a变成严格单调上升等同于把b变成单调不降

唉,实在不会

https://pan.baidu.com/share/link?uk=2651016602&shareid=1490516411

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

点击跳转

先考虑每种硬币可以用无数次

f_i表示金额为i有多少种方案

f_i = \sum_{j=1}^4 f_{i-c[j](i \ge c_j)}

我们再来考虑硬币使用次数有限制怎么办

不合法的情况有:

1超额

1,2超额

1,3超额

1,4超额

1,2,3超额

1,2,4超额

1,3,4超额

1,2,3,4超额

...

要注意的是在多种硬币限制的情况下可能会减去多次,或加上多次

比如1超额,2超额,(1,2同时超额被减去两次,这是就要加回来

(1,2,3)(1,2,4)又是多算的...

是不是更直观的了解了容斥?

为了方便,我们可以枚举二进制下状态来更加优美实现。

(当有奇数种不合法的时候减去,偶数种不合法时加上)

5/10
Search
search