最開(kāi)始我們先旋轉(zhuǎn)一下這張桌子，使得 $A_1=A_{n+1}=\max \{A_i\}$。

這是非常有效的，因?yàn)槲覀儼循h(huán)就變成鏈，只要到達(dá)了鏈的任意一端 $1/n+1$ 就肯定會(huì)結(jié)束游戲。

定義 $E_i:$ 從 $i$ 開(kāi)始游戲，運(yùn)用最優(yōu)策略，結(jié)束游戲的期望收益。

顯然，$E_1=A_1,E_{n+1}=A_{n+1},{?}_{1\le i\le n}{E}_i=\max (A_i,\frac{E_{i?1}+E_{i+1}}{2}?B_i)$。

---

簡(jiǎn)化問(wèn)題，假設(shè)沒(méi)有這個(gè) $B_i$ 存在。

把 $i$ 看成 $(i,A_i)$ 放到二維平面內(nèi)，則答案 $E_i$ 就是 $i$ 為橫坐標(biāo)時(shí)在這些點(diǎn)維護(hù)出的凸殼上的縱坐標(biāo)。

畫(huà)畫(huà)圖就知道了。

維護(hù)凸殼以及求解答案是可以在線性時(shí)間內(nèi)完成的。

---

考慮將當(dāng)前復(fù)雜問(wèn)題往簡(jiǎn)單問(wèn)題上靠攏。

能否構(gòu)造出一個(gè)新形式的 $F_i$ 將 $B_i$ 抵消掉，即 $F_i=\max (G_i,\frac{F_{i?1}+F_{i+1}}{2})$，再通過(guò) $F_i$ 反推回 $E_i$。

$$\begin{gathered} E_i?C_i=\max (A_i?C_i,\frac{E_{i?1}+E_{i+1}}{2}?C_i?B_i) \\ ? \end{gathered}$$$$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}?C_i?B_i)$$

（因?yàn)?$B_i$ 是常量，前面的系數(shù)是不帶 $i$ 的任一次方的，所以我們構(gòu)造的時(shí)候應(yīng)該先考慮不出現(xiàn)帶 $i$ 系數(shù)的形式）

發(fā)現(xiàn)只要令 ${?}_{1\le i\le n}\frac{C_{i?1}+C_{i+1}}{2}?C_i?B_i=0$ 就能達(dá)到目的。

$?C_i?C_{i?1}+2B_i=C_{i+1}?C_i$ 且 $C_2=C_1=0$，這樣 $C$ 就遞推出來(lái)了。

令 $F_i=E_i?C_i$，則 $F_i=\max (A_i?C_i,\frac{F_{i?1}+F_{i+1}}{2})$，以 $(i,F_i)$ 構(gòu)造凸殼即可線性求解。

先維護(hù)出凸殼，后再挨個(gè)求縱坐標(biāo)。

#include <bits/stdc++.h> using namespace std; #define int long long #define double long double #define maxn 200005 int A[maxn], B[maxn], C[maxn], s[maxn]; double ans; int n;signed main() {scanf( "%lld", &n );for( int i = 1;i <= n;i ++ ) scanf( "%lld", &A[i] );for( int i = 1;i <= n;i ++ ) scanf( "%lld", &B[i] );int id = max_element( A + 1, A + n + 1 ) - A;rotate( A + 1, A + id, A + n + 1 );rotate( B + 1, B + id, B + n + 1 );A[n + 1] = A[1], B[n + 1] = B[1];for( int i = 3;i <= n + 1;i ++ ) C[i] = ( B[i - 1] + C[i - 1] << 1 ) - C[i - 2];for( int i = 1;i <= n + 1;i ++ ) A[i] -= C[i];int top = 0;s[++ top] = 1;for( int i = 2;i <= n + 1;i ++ ) {while( top and (A[i] - A[s[top]]) * (s[top] - s[top - 1]) > (A[s[top]] - A[s[top - 1]]) * (i - s[top]) ) top --;/*( A[i]-A[s[top]] ) / ( i-s[top] ) k1 of new line( A[s[top]]-A[s[top-1]] ) / ( s[top]-s[top-1]) k1 of latest lineif k1>k2 throw k2*/s[++ top] = i;}double ans = 0;top = 0;for( int i = 1;i <= n;i ++ ) {if( s[top + 1] == i ) top ++;ans += (A[s[top + 1]] - A[s[top]]) * 1.0 / (s[top + 1] - s[top] ) * (i - s[top]) + A[s[top]];//將凸包上的一條邊抽變成從原點(diǎn)開(kāi)始計(jì)算ans += C[i];}printf( "%.12Lf\n", ans / n );return 0; }

總結(jié)

以上是生活随笔為你收集整理的AGC044E Pandom Pawn（期望+凸包）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。