# [Learning Notes] Monotonicity of Decision-Making + [Problem Solution] Luo Gu3515: [POI2011]Lightning Conductor

Theme portal
Decision-making monotonicity optimization qwq
The monotonicity of decision is the current state I I i, two decision j, K (j & lt; k) j, K (j & lt; k) j, K (j < k). if K is better, then J will never reverse when I increases
This is the time to satisfy the monotony of decision-making
Then it is obtained that each decision corresponds to an interval so that the decision is the optimal solution for the state in the interval.

A bit of a mystery.
fi=max(aj+∣j−i∣)f_i=max(a_j+\sqrt{|j-i|})fi​=max(aj​+∣j−i∣​)
The way to get rid of absolute value is to do it over and over again.
Open a monotone queue with triples {l,r,pl,r,pl,r,p} to represent the corresponding interval [l,r][l,r][l,r]
Some properties and practices can be obtained.

• All the intervals put together are [1,n][1,n][1,n]
• iii enumerates + + q[h].l once per enumeration, and deletes if the corresponding interval of the team leader is empty
• For each state iii, the optimal decision is the head of the team
• The condition for adding i-decision at the end of the team is that decision I is better for state n than for decision-making end-to-state n.
• Then the corresponding interval is updated by dichotomy search critical value

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];

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(){