最初在HDU的ACM模板上看到这个分治的DP优化
用这个的前提是不强制在线（f[i]不由前面的f转移过来）且决策单调
[forall jin left[ ext{1,}n
ight] \,\,p_ige aleft[ j
ight] -aleft[ i
ight] -sqrt{|i-j|}
]
[p_ige max ( aleft[ j
ight] -aleft[ i
ight] -sqrt{|i-j|} )
]
[p_ige max left( max left( aleft[ j
ight] -aleft[ i
ight] -sqrt{i-j}
ight) ,max left( aleft[ j
ight] -aleft[ i
ight] -sqrt{j-i}
ight)
ight)
]
第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], '
';
#ifdef LOCAL_DEBUG
fprintf(stderr, "
time:%.5lfms", (clock() - tim1) / (1.0 * CLOCKS_PER_SEC) * 1000);
#endif
return 0;
}