django个人博客网站开发部署源码,山西谷歌seo,wdcp 配置网站,产品设计说明题目链接 BZOJ2216 题解 学过高中数学都应知道#xff0c;我们要求\(p\)的极值#xff0c;参变分离为\[h_j sqrt{|i - j|} - h_i \le p\] 实际上就是求\(h_j sqrt{|i - j|} - h_i\)的最大值 就可以设\(f[i]\)表示对\(i\)最大的该式的值 绝对值通常要去掉#xff0c;一般可… 题目链接 BZOJ2216 题解 学过高中数学都应知道我们要求\(p\)的极值参变分离为\[h_j sqrt{|i - j|} - h_i \le p\] 实际上就是求\(h_j sqrt{|i - j|} - h_i\)的最大值 就可以设\(f[i]\)表示对\(i\)最大的该式的值 绝对值通常要去掉一般可以通过方向性我们只需每次转移时令\(i j\)正反转移两次即可 现在式子变为\[f[i] max\{h_j \sqrt{i - j}\} - h_i\] 发现\(\sqrt{i - j}\)依旧无法处理无法展开使用我们喜闻乐见的斜率优化 此时就可以考虑这个式子是否具有决策单调性 我们考虑对于\(ii\)我们的决策为\(h_j sqrt{i - j}\) 那么对于\(forall k j\)有\(h_k sqrt{i - k} h_j sqrt{i - j}\) 现在我们用\(i\)替换\(i\) 式子变为\(h_k sqrt{i - k}\)和\(h_j sqrt{i - j}\)\(h_k\)和\(h_j\)是没有变化的如果\(sqrt{i - j}\)的增长比\(sqrt{i - k}\)的增长要快我们就可认定\(i\)替换\(i\)后\(k\)依旧无法作为最优决策 考虑函数\[f(x) \sqrt{x}\]\[f(x) \frac{1}{2\sqrt{x}}\] 显然当\(x\)越大增长率越慢而\(i - k i - j\)\(\sqrt{i - j}\)的增长的确比\(\sqrt{i - k}\)的增长要快 得证 所以用队列维护三元组优化即可 复杂度\(O(nlogn)\) #includealgorithm
#includeiostream
#includecstring
#includecstdio
#includecmath
#includemap
#define Redge(u) for (int k h[u],to; k; k ed[k].nxt)
#define REP(i,n) for (int i 1; i (n); i)
#define mp(a,b) make_pairint,int(a,b)
#define cls(s) memset(s,0,sizeof(s))
#define cp pairint,int
#define LL long long int
using namespace std;
const int maxn 500005,maxm 100005;
inline int read(){int out 0,flag 1; char c getchar();while (c 48 || c 57){if (c -) flag -1; c getchar();}while (c 48 c 57){out (out 3) (out 1) c - 48; c getchar();}return out * flag;
}
double f[maxn],h[maxn];
int n,head,tail,ans[maxn];
struct tri{int l,r,pos;}q[maxn 1];
inline double cal(int i,int j){return h[j] sqrt(i - j) - h[i];
}
inline bool check(int pos,int i,int j){return cal(pos,i) cal(pos,j);
}
void work(){q[head tail 0] (tri){1,n,1};tri u;for (int i 1; i n; i){ans[i] max(ans[i],(int)ceil(cal(i,q[head].pos)));q[head].l;if (q[head].l q[head].r) head;while (head tail){u q[tail--];if (!check(u.r,i,u.pos)){q[tail] u;if (u.r 1 n) q[tail] (tri){u.r 1,n,i};break;}if (check(u.l,i,u.pos)){if (head tail){q[tail] (tri){i 1,n,i};break;}continue;}else {int l u.l,r u.r,mid;while (l r){mid l r 1;if (check(mid,i,u.pos)) r mid;else l mid 1;}q[tail] (tri){u.l,l - 1,u.pos};q[tail] (tri){l,n,i};break;}}}
}
int main(){n read();for (int i 1; i n; i) h[i] read();work();reverse(h 1,h 1 n);reverse(ans 1,ans 1 n);work();for (int i n; i; i--)printf(%d\n,ans[i]);return 0;
}转载于:https://www.cnblogs.com/Mychael/p/9210591.html
