【学习笔记】决策单调性+【题解】LuoGu3515：[POI2011]Lightning Conductor

原题传送门
决策单调性优化qwq
决策单调性就是当前状态$i$，两个决策$j,k(j<k)$，如果k更优，那么在i增大时，j永远不会逆袭
这个时候满足决策单调性
那么得到每个决策都对应一个区间使得这个决策对于区间里的状态是最优解

好讲一下这道题目
有点迷
$f_i=max(a_j+\sqrt{|j-i|})$
把绝对值去掉的方法是正着做一遍反着做一遍
开个单调队列，存三元组{$l,r,p$}，表示决策p对应区间$[l,r]$
可以得到一些性质及其做法

• 所有区间拼到一起是$[1,n]$
• $i$每枚举一次++q[h].l，并且若队首对应区间为空，则删除
• 对于每个状态$i$，最优决策即队首
• 在队尾加入i决策的条件是决策i对状态n比决策队尾对状态n更优
• 然后二分查找临界值更新对应区间

Code：

#include <bits/stdc++.h>
#define maxn 500010
using namespace std;
struct data{
	int l, r, p;
}q[maxn];
int n, a[maxn];
double f[maxn], g[maxn];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

double calc(int j, int i){ return a[j] - a[i] + sqrt(abs(i - j)); }

int find(data t, int x){
	int l = t.l, r = t.r;
	while (l <= r){
		int mid = (l + r) >> 1;
		if (calc(t.p, mid) > calc(x, mid)) l = mid + 1; else r = mid - 1;
	}
	return l;
}

void Dp(double *dp){
	int h = 1, t = 0;
	for (int i = 1; i <= n; ++i){
		if (h <= t && ++q[h].l > q[h].r) ++h;
		if (h > t || calc(q[t].p, n) < calc(i, n)){
			while (h <= t && calc(q[t].p, q[t].l) < calc(i, q[t].l)) --t;
			if (h > t) q[++t] = (data){i, n, i}; else{
				int tmp = find(q[t], i);
				q[t].r = tmp - 1;
				q[++t] = (data){tmp, n, i};
			}	
		}
		dp[i] = calc(q[h].p, i);
	}
}

int main(){
	n = read();
	for (int i = 1; i <= n; ++i) a[i] = read();
	Dp(f);
	reverse(a + 1, a + 1 + n);
	Dp(g);
	for (int i = 1; i <= n; ++i) printf("%d\n", max(0, (int)ceil(max(f[i], g[n + 1 - i]))));
	return 0;
}