在 \(DP\) 的世界里
有一种题需要单调队列优化 \(DP\)
一般在此时,\(f_i\) 和它的决策集合 \(f_j\) 在转移时 \(i\) 不和 \(j\) 粘在一起(即所有的 \(j\) 转移到 \(i\)时 关于\(j\) 的部分全都与 \(i\)无关),
果真如此,我们就可以用单调队列优化,留下可能用到的更有决策
而很多情况下 \(i,j\) 有联系,\(i\) 对于不同的 \(j\) ,转移计入的贡献和 \(i,j\) 都有联系,如
\(f_i = \min_{j=1}^{j<i} f_j+s_{i-1}-s_j+|h_i - h_{j-1}|\)
此时单调队列就无用武之地了
那怎么办
各种奇妙的优化
本文我们来学习线段树优化 \(DP\),解决上面问题
在例题中感受美
题目大意:
将序列 \(H\) 划分为两个可空集合。
对于一个集合 \(S={P1,P2,…P|S|}\),其中要求 \(P1<P2<…<P|S|\),它的花费是 \(\sum_{i=1}^{|S|} |H_{P_i}-H_{P_{i-1}}|\)
最小化花费
解法:
还好的 \(dp\)
设 \(f_i\) 表示处理完 \(1--i\) 个元素的最小花费
那么转移考虑当前的 \(i\) 所属集合前一个元素是谁
枚举一个 \(j\), \(j-1\) 和 \(i\) 同属一个集合
那么转移就是 \(f_i = \min_{j=1}^{j<i} f_j+s_{i-1}-s_j+|h_i - h_{j-1}|\)
其中 \(s_i = s_{i-1} + |h_i - h_{i-1}|\)
一眼望去 \(O(n^2)\)
再望,绝对值太糟糕(单调队列挂了花)
怎办?
去!
用线段树维护
······
不会啊?
如何用线段树
君不见,绝对值从天上来,纠缠 \((i,j)\) 不可休······
插!
分类讨论,绝对值分开,把式子变好看,这样 \(i,j\) 就分开了
\(1\) 若 \(h_i > h_j\) 则 \(f_i = f_j+s_{i-1}-s_j+h_i-h_{j-1}\)
整理得 \(f_i = (s_{i-1}+h_i)+(f_j-s_j-h_{j-1})\)
\(2\) 若 \(h_i > h_j\) 则 \(f_i = f_j+s_{i-1}-s_j-h_i+h_{j-1}\)
整理得 \(f_i = (s_{i-1}-h_i)+(f_j-s_j+h_{j-1})\)
总算把 \((i,j)\) 分开了
此时做商量
如何让 \(1\) 式最小,因为决定于 \(j\),所以让后面一堆最小
发现可以用线段树维护 \(f_j-s_j-h_{j-1}\) 的最小值
因为判定时和 \(j-1\) 有关,所以维护以 \(h_{j-1}\) 为下标的权值线段树
具体来说就是在 \(h_{j-1}\) 的位置插入值 \(f_j-s_j-h_{j-1}\)
因为顺序枚举,所以算完一个插一个,保证正确性
只需取出线段树中 \(0--h_{i}\) 的最小值即可
\(2\) 式同理(再开一棵权值线段树,因为另一种 \(j\) 的贡献长得不一样)
#pragma GCC optimize(2)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 500000;
int n , h[N + 5] , id[N + 5];
LL f[N + 5] , s[N + 5];
inline LL Min(LL x , LL y) { return x < y ? x : y; }
inline int Abs(int x) { return x < 0 ? -x : x; }
struct node{ int l , r; }e[N + 5];
struct tree{
LL tr[(N << 2) + 5];
inline void full() { memset(tr , 120 , sizeof(tr)); }
inline void change(int k , int l , int r , int x , LL v)
{
tr[k] = Min(tr[k] , v);
if (l == r) return;
register int mid = (l + r) >> 1;
if (x <= mid) change(k << 1 , l , mid , x , v);
else change(k << 1 | 1 , mid + 1 , r , x , v);
}
inline LL query(int k , int l , int r , int x , int y)
{
if (l >= x && r <= y) return tr[k];
register int mid = (l + r) >> 1;
register LL res = 1e18;
if (x <= mid) res = Min(res , query(k << 1 , l , mid , x , y));
if (y > mid) res = Min(res , query(k << 1 | 1 , mid + 1 , r , x , y));
return res;
}
}p,q;
inline int read()
{
register char ch = getchar();
register LL res = 0;
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9') res = res * 10 + ch - '0' , ch = getchar();
return (int)res;
}
inline bool cmp(node x , node y) { return x.l < y.l; }
int main()
{
// freopen("a.in" , "r" , stdin);
n = read();
for(register int i = 1; i <= n; i++)
{
h[i] = read() , e[i].l = h[i] , e[i].r = i;
s[i] = s[i - 1] + (LL)Abs(h[i] - h[i - 1]);
}
sort(e + 1 , e + n + 1 , cmp);
for(register int i = 1; i <= n; i++) id[e[i].r] = i;
q.full() , p.full();
q.change(1 , 0 , n , 0 , 0);
p.change(1 , 0 , n , 0 , 0);
f[0] = 0;
for(register int i = 1; i <= n; i++)
{
LL x = q.query(1 , 0 , n , 0 , id[i]);
LL y = p.query(1 , 0 , n , id[i] , n);
f[i] = Min(s[i - 1] + h[i] + x , s[i - 1] - h[i] + y);
q.change(1 , 0 , n , id[i - 1] , f[i] - s[i] - h[i - 1]);
p.change(1 , 0 , n , id[i - 1] , f[i] - s[i] + h[i - 1]);
}
for(register int i = 1; i <= n; i++) f[n] = Min(f[n] , f[i] + s[n] - s[i]);
printf("%lld" , f[n]);
}
很多时候,线段树优化 \(DP\) 的具体方法因题而异,不可一概而论
要想更好的掌握,就要多做题
手机扫一扫
移动阅读更方便
你可能感兴趣的文章