CF1810G The Maximum Prefix 题解

link T3 desu. translated ver

好玩且 Educational 的题。

引用自 https://www.luogu.com.cn/article/tl6zx3q0 和 https://www.luogu.com.cn/article/mh3i34s3。有修改。

首先先分析下这个“最大前缀和”，按照最朴素的思路就是扫一遍每个前缀，然后记录一下当前的 前缀和 $s$ 与前面的 最大前缀和 $mx$。但是如果你一直陷在这个思路上你就似了，因为按照这个思路做，你 DP 状态里的两个维度是没有任何办法省掉当中任何一个的（不然他会出错），所以哪怕解决单个 $k=n$ 的问题都至少需要 $O(n^3)$。

考虑换一个角度处理“最大前缀和”，我们可以考虑从后往前 dp，令 $dp_{i,j}$ 表示 $[i,n]$ 后缀的最大前缀和为 $j$ 的概率。那么转移方程为：

$$\begin{cases} p_i\cdot dp_{i+1,j}\rightarrow dp_{i,j+1} \\ (1−p_i)\cdot dp_{i+1,j}\rightarrow dp_{i,max(j−1,0)} \end{cases}$$

初值 $dp_{n+1,0}=1$，最终 $ans=\sum_{i=0}^n h_i\cdot dp_{1,i}$。

这样子的复杂度就变为了单次 $O(n^2)$。

但是我们这样算的只是 $k=n$ 时的答案，如果直接使用这玩意计算 $k\leq n$ 是 $O(n^3)$ 的。

那么因为我菜，我们可以画个图，考虑这玩意怎么优化：

我们不难发现，实际上每一个长度的初值的都是靠在最右边的“根”，$dp$ 过程就是通过这个“根”向底扩展的。

在这张图里面，很明显，优化点在与将 $dp$ 改为存期望值。我们不妨从底向上推 $dp$，从而可以通过访问 $dp_{l+1,0}$ 来求得期望值。

那么我们通过图片可以推出：

• 如果 $j\neq 0$：

  $dp_{i,j}=dp_{i-1,j+1}\cdot p_{i-1}+dp_{i-1,j-1}\cdot (1-p_{i-1})$

• 如果 $j=0$：

  $dp_{i,j}=dp_{i-1,1}\cdot p_{i-1}+dp_{i-1,0}\cdot (1-p_{i-1})$

初始 $dp_{0,i}=h_i$，然后这题就做完了。

Code:

ldb dp[maxn][maxn];
void solve2(){
	for(int i=0;i<=n;++i) dp[1][i]=h[i];
	for(int i=2;i<=n+1;++i){
		ldb p=px[i-1]/py[i-1];
		ldb obp=1-p;
		for(int j=0;j<=n+1-i;++j){
			if(j==0) dp[i][j]=dp[i-1][1]*p+dp[i-1][0]*obp;
			else dp[i][j]=dp[i-1][j+1]*p+dp[i-1][j-1]*obp;
		}
	}
}

int main(){
    /*...*/
	for(int i=2;i<=n+1;++i)	printf("%Lf ",dp[i][0]);
    return 0;
}

%P 什么的自己去看吧哈哈。

sub