\(TXX\) 讲课。\(2024 \ 7 \ 23.\)
\(T1.\)
首先你可以考虑用 \(dp.\) 先记棋子脚下的位置为 \(v\)，动态规划方程：
\(f_i=\max\{\dfrac{1}{2}(f_{i-1}+f_{i+1}),v_i\}\)
利用这个方程，我们可以把他用 \((i,f_i)\) 的画在平面上。
然后观察这个平面，发现 \(i\) 位置上面的答案也就是凸包位置。凸包直接做就好了。
用叉积做凸包。很简单的求解。
注意卡精度。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,K=5e4;
int n,v[N],stk[N],prv[N],nxt[N],top,tmp=1;
struct point{
int x,y;
point operator -(point a){return point(x-a.x,y-a.y);}
int operator *(point a){return x*a.y-y*a.x;}
point(int X=0,int Y=0){x=X,y=Y;}
}p[N];
bool cmp(point a,point b){if(a.x^b.x)return a.x<b.x;return a.y<b.y;}
signed main(){
cin>>n;
p[1]=point(1,0);
for(int i=2;i<=n+1;++i)cin>>v[i],v[i]*=1e5,p[i]=point(i,v[i]);
n+=2,p[n]=point(n,0);
stk[top=1]=1;
for(int i=2;i<=n;++i){
while(top>1&&(p[stk[top]]-p[stk[top-1]])*(p[i]-p[stk[top]])>0)--top;
stk[++top]=i;
}
int j=2;
for(int i=2;i<n;++i){
while(stk[j]<=i)++j;
printf("%lld\n",(int)(v[stk[j-1]]+(i-stk[j-1])*(v[stk[j]]-v[stk[j-1]])*1.0/(stk[j]-stk[j-1])));
}
}