一道简单的期望DP题。。但是我这种题还要看别人的题解。。毕竟DP能力太差
考虑我们已经确定好了前k-1位的期望得分，那么当前第k位有两种情况:
1.操作成功为1，这么做的贡献就等于前面连续1的个数加上1后再三次方的得分然后减去前面的得分期望
2.操作失败为0，那么贡献为0
然后我们需要维护x,x2两个量，然后因为期望的线性性，我们每一次直接加上就好了
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
int n;
double a[100005],x[100005],x2[100005],dp[100005];
int main(){
freopen("4318.in","r",stdin);
freopen("4318.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lf",&a[i]);
for(int i=1;i<=n;i++){
x[i]=(x[i-1]+1)*a[i];
x2[i]=(x2[i-1]+2*x[i-1]+1)*a[i];
dp[i]=dp[i-1]+(3*x2[i-1]+3*x[i-1]+1)*a[i];
}
printf("%.1lf\n",dp[n]);
return 0;
}
评论 (0)
