首页 > 代码库 > 【BZOJ】4318: OSU!
【BZOJ】4318: OSU!
【算法】期望DP
【题解】
OSU!(误)
原本在纠结长度很不好算啊……x有好多种可能,新增一个不知道加多少QAQ
后来发现我们不是在算期望嘛……不是就算期望长度就好了嘛。
f[i]为加入第i个后的收益。
g[i]为加入第i个后的期望长度。
加入一个i=1的收益为x^3-(x-1)^3=3x^2-3x+1
注意不能直接g[i]*g[i]表示平方,因为平方不是线性运算,期望的平方≠平方的期望。
g2[i]为期望长度的平方。
推导方式中(x-1)--->x和x--->(x+1)的区别:
我们设置g2[i]是为了避免直接对期望平方,而采用递推的方式保持线性运算。
递推的方式是p(i)=[p(i-1)...]*x+0*(1-x),所以[p(i-1)...]的部分是直接后面接一个x的(默认概率为1)
如果是(x-1)--->x的话,推导过程中使用了x的元素,而x的元素已经加入了x的概率计算。
所以必须采用x--->(x+1)的方式,使概率计算不重复。
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxn=100010; double f[maxn],g[maxn],g2[maxn]; int n; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { double x; scanf("%lf",&x); g[i]=(g[i-1]+1)*x; g2[i]=(g2[i-1]+2*g[i-1]+1)*x; f[i]=f[i-1]+(3*g2[i-1]+3*g[i-1]+1)*x; } printf("%.1lf",f[n]); return 0; }
【BZOJ】4318: OSU!
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。