luogu1654 OSU!

DP 期望

题面

一共有$n$次操作，每次操作只有成功与失败之分，成功对应$1$，失败对应$0$，$n$次操作对应为$1$个长度为$n$的$01$串。
在这个串中连续的$X$个$1$可以贡献$X^3$的分数，这$x$个$1$不能被其他连续的$1$所包含。
现在给出$n$，以及每个操作的成功率，请你输出期望分数，输出四舍五入后保留$1$位小数。

• $n\leq10^5$

解析

丽洁姐姐的题目套路真多
想想如果又添一个$1$会怎么样？
贡献将变为为$(x+1)^3=x^3+3x^2+3x+1$
实际增加量为$3x^2+3x+1$

这个玩意怎么求呢？
设$x1_i$表示以$i$为结尾的$1$串的期望长度。(表增量）
$x2_i$表示以$i$为结尾的$1$串期望长度的平方。（表增量）
$x3_i$表示到$i$时串的期望得分。（累计答案）
$x1[i]=(x1[i-1]+1)*p$

$x_2$的转移可以应用完全平方公式：
$x2[i]=(x2[i-1]+2*x1[i-1]+1)*p$

F3的转移就是概率乘结果：
$x3[i]=x3[i-1]*(1-p)+(x3[i-1]+3*x2[i-1]+3*x1[i-1]+1)*p$

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define pb(a) push_back(a)
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=1e5+100;
int n;
double x1[N],x2[N],x3[N],p;
il int gi()
{
  re int x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
int main()
{
  n=gi();
  fp(i,1,n)
    {
      scanf("%lf",&p);
      x1[i]=(x1[i-1]+1)*p;
      x2[i]=(x2[i-1]+2*x1[i-1]+1)*p;
      x3[i]=x3[i-1]+(3*x2[i-1]+3*x1[i-1]+1)*p;
    }
  printf("%.1f\n",x3[n]);
  return 0;
}