最初在HDU的ACM模板上看到这个分治的DP优化

用这个的前提是不强制在线（f[i]不由前面的f转移过来）且决策单调

\[ \forall j\in \left[ \text{1,}n \right] \,\,p_i\ge a\left[ j \right] -a\left[ i \right] -\sqrt{|i-j|} \]

\[ p_i\ge \max ( a\left[ j \right] -a\left[ i \right] -\sqrt{|i-j|} ) \]

\[ p_i\ge \max \left( \max \left( a\left[ j \right] -a\left[ i \right] -\sqrt{i-j} \right) ,\max \left( a\left[ j \right] -a\left[ i \right] -\sqrt{j-i} \right) \right) \]

第15行和第7行 >=不能写成> 因为决策点单调，即使两个点的dp值相同，也要更新决策点

int a[MAXN * 5], n;int dp1[MAXN * 5], dp2[MAXN * 5];inline void DP1(int l, int r, int dl, int dr) {  if (l > r) return ;  int Max = 0; lf mx = 0;  lop(i, dl, min(dr, mid)) if (a[i] - a[mid] + sqrt(mid - i) >= mx) Max = i, mx = a[i] - a[mid] + sqrt(mid - i);  chmax(dp1[mid], a[Max] - a[mid] + ceil(sqrt(mid - Max)));  DP1(l, mid - 1, dl, Max), DP1(mid + 1, r, Max, dr);}inline void DP2(int l, int r, int dl, int dr) {  if (l > r) return ;  int Max = 0; lf mx = 0;  dlop(i, dr, max(dl, mid)) if (a[i] - a[mid] + sqrt(i - mid) >= mx) Max = i, mx = a[i] - a[mid] + sqrt(i - mid);  chmax(dp2[mid], a[Max] - a[mid] + ceil(sqrt(Max - mid)));  chmax(dp2[mid], dp1[mid]);  DP2(l, mid - 1, dl, Max), DP2(mid + 1, r, Max, dr);}int main() {#ifdef LOCAL_DEBUG  // freopen("data.in", "r", stdin), freopen("data.out", "w", stdout);  Dbg = 1; uint tim1 = clock();#endif  in, n;  lop(i, 1, n) in, a[i];  DP1(1, n, 1, n);  DP2(1, n, 1, n);  lop(i, 1, n) out, dp2[i], '\n';#ifdef LOCAL_DEBUG  fprintf(stderr, "\ntime:%.5lfms", (clock() - tim1) / (1.0 * CLOCKS_PER_SEC) * 1000);#endif  return 0;}