这两道题是一个类型的，所以放到一起写了。
Balance Beam P
我们不算那个什么关键点了，直接设 \(E_i\) 为最优策略下从 \(i\) 开始的报酬。那么我们有 \(E_0=E_{n+1}=0\)，同时考虑这一步的决策，如果走，那么期望为 \(\dfrac{E_{i-1}+E_{i+1}}{2}\)，如果不走，报酬是 \(f_i\)。
所以我们有 \[
E_{i}=\max(\frac{E_{i-1}+E_{i+1}}{2},f_i)\quad (1\leqslant i\leqslant n)
\] 我们有以下定论：点集 \(\{(i,E_i)\}\) 在点集 \(\{(i,f_i)\}\cup\{(0,0),(n+1,0)\}\) 所构成的凸包上。
我们不难发现 \(E_i\) 等于 \((i,f_i)\) 和经过 \((i-1,E_{i-1})\) 与 \((i+1,E_{i+1})\) 两点的直线在 \(x=i\) 出的纵坐标的较大值，则其一定是凸的；同时不难发现，\(\{(i,f_i)\}\cup\{(0,0),(n+1,0)\}\) 构成的凸包一定满足上述条件。
下面我们证明这样的点集是唯一的。为此我们扩展一下状态：给定平面中 \(n\) 个点 \((x_i,y_i)\) 和点 \((x_0,f_0),(x_{n+1},f_{n+1})\)，满足 \(x_i\) 互不相同且从小到大排列。设\(f_i=\max(y_i,\dfrac{x_{i+1}-x_i}{x_{i+1}-x_{i-1}}f_{i-1}+\dfrac{x_i-x_{i-1}}{x_{i+1}-x_{i-1}}f_{i+1})\)，从图形意义上依旧是相邻的两个点形成直线和给定点的较高点。则我们只需要证明 \(\{(x_i,f_i)\}\) 的每一个顶点都是给定点集中的点。我们考虑归纳证明。
当 \(n=1\) 时显然成立。
当 \(n>1\) 时，考虑任意添加最后一个点，如果其在前 \(n+1\) 个点形成的凸包内部，则继续；反之新形成的凸包一定由原凸包上点的子集和新加入的点组成。这样一定不会有不属于原点集的点。
所以我们只需要维护原点集的凸包，这个可以线性实现。
代码（这题卡精度最后输出的时候不要用 double 要用 __int128）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include<bits/stdc++.h>
using namespace std;
typedef __int128 ll;
ll a[200005];
int q[200005],tl;
double f[200005];
ll crs(int x,int y,int z){return ((y-x)*(a[y]-a[z])-(y-z)*(a[y]-a[x]));}
void add(int x)
{
while(tl>1&&crs(q[tl-1],q[tl],x)<=0)tl--;
q[++tl]=x;
}
void write(__int128 x)
{
if(x<=9){putchar('0'+x);return;}
write(x/10);
putchar('0'+x%10);
}
int main()
{
int n;
scanf("%d",&n);
q[tl=1]=0;
for(int i=1;i<=n;i++)
{
long long x;
scanf("%lld",&x);
a[i]=x;
a[i]*=100000;
add(i);
}
add(n+1);
int now=1;
for(int i=1;i<=n;i++)
{
while(q[now+1]<=i)now++;
write(((((q[now+1]-i)*a[q[now]])+(i-q[now])*a[q[now+1]])/(q[now+1]-q[now])));
puts("");
}
return 0;
}
|
Random Pawn
上一道题的加强版。
首先我们发现，如果走到了环上的最大值，则一定会停止，所以我们可以在最大值处破环为链（令 \(0\) 和 \(n\) 都为最大值）。
令 \(E_i\) 为从 \(i\) 开始的期望，那么我们现在也可以写出转移： \[
E_i=\max(A_i,\frac{E_{i-1}+E_{i+1}}{2}-B_i)
\] 如果没有 \(B_i\)，那就是上一道题了，我们现在考虑把 \(B_i\) 消掉。
我们尝试构造一个数列 \(\{C_i\}\)，那么有 \[
E_i-C_i=\max(A_i-C_i,\frac{E_{i-1}-C_{i-1}+E_{i+1}-C_{i+1}}{2}+\frac{C_{i-1}+C_{i+1}}{2}-B_i-C_i)
\] 如果我们的 \({C_n}\) 能让 \(\dfrac{C_{i-1}+C_{i+1}}{2}-B_i-C_i=0\)，设 \(F_i=E_i-C_i,G_i=A_i-C_i\)，则有 \[
F_i=\max(G_i,\frac{F_{i-1}+F_{i+1}}{2})
\] 这个就是上一道题的形式了，\(C_i\) 可以随便确定 \(C_0,C_1\) 然后直接递推得到（\(C_i=2C_{i-1}+2B_{i-1}-C_{i-2}\)）。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll tmp1[200005],tmp2[200005],a[200005],b[200005],c[200005],g[200005];
int q[200005],tl;
ll crs(int x,int y,int z){return ((y-x)*(g[y]-g[z])-(y-z)*(g[y]-g[x]));}
void add(int x)
{
while(tl>1&&crs(q[tl-1],q[tl],x)<=0)tl--;
q[++tl]=x;
}
int main()
{
int n,mx=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&tmp1[i]);
if(tmp1[i]>tmp1[mx])mx=i;
}
for(int i=1;i<=n;i++)scanf("%lld",&tmp2[i]);
for(int i=mx;i<=n;i++)a[i-mx]=tmp1[i],b[i-mx]=tmp2[i];
for(int i=1;i<=mx;i++)a[n-mx+i]=tmp1[i],b[n-mx+i]=tmp2[i];
for(int i=2;i<=n;i++)c[i]=2*c[i-1]+2*b[i-1]-c[i-2];
for(int i=0;i<=n;i++)g[i]=a[i]-c[i],add(i);
int now=1;
double res=0;
for(int i=0;i<n;i++)
{
while(q[now+1]<=i)now++;
res+=((((q[now+1]-i)*g[q[now]])+(i-q[now])*g[q[now+1]])*1.0/(q[now+1]-q[now]))+c[i];
}
printf("%.12lf",res/n);
return 0;
}
|