2020-2021:teams:i_dont_know_png:cerc2017
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:i_dont_know_png:cerc2017 [2020/05/06 14:24] nikkukun |
2020-2021:teams:i_dont_know_png:cerc2017 [2020/05/22 20:14] (当前版本) potassium fix typos |
||
|---|---|---|---|
| 行 125: | 行 125: | ||
| ==== 解题思路 ==== | ==== 解题思路 ==== | ||
| - | 首先考虑扩展区间$[i,i+1]$，不妨设$a_i<a_{i+1}$，则要使得$[i,i+1]$区间位于连续区间中，区间$[l,r]=$$[min_{a_i\leq j\leq a_{i+1}}pos_j,max_{a_i\leq j\leq a_{i+1}}pos_j]$必然也位于同一个区间中，这里的$l,r$容易通过$rmq$求得。可以说，区间$[i,i+1]$依赖区间$[l,l+1],[l+1,l+2],...,[r-1,r]$。 | + | 首先考虑扩展区间$[i,i+1]$，不妨设$a_i<a_{i+1}$，则要使得$[i,i+1]$区间位于连续区间中，区间$[l,r]=$$[min_{a_i\leq j\leq a_{i+1}}pos_j,max_{a_i\leq j\leq a_{i+1}}pos_j]$必然也位于同一个区间中，这里的$l,r$容易通过$rmq$求得。可以说，区间$[i,i+1]$依赖区间$[l,l+1],[l+1,l+2],\ldots,[r-1,r]$。 |
| 把区间$[i,i+1]$抽象为一个节点，对于每一个$i$，求出其依赖区间，连边建图缩点后转化成$DAG$上的动态规划问题，从叶节点向上不断更新实际依赖区间即可。 | 把区间$[i,i+1]$抽象为一个节点，对于每一个$i$，求出其依赖区间，连边建图缩点后转化成$DAG$上的动态规划问题，从叶节点向上不断更新实际依赖区间即可。 | ||
2020-2021/teams/i_dont_know_png/cerc2017.1588746276.txt.gz · 最后更改: 2020/05/06 14:24 由 nikkukun
