社区讨论

求助,关于本题的状态

P3750[六省联考 2017] 分手是祝愿参与者 1已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lztsnqmd
此快照首次捕获于
2024/08/14 19:54
2 年前
此快照最后确认于
2024/08/14 22:05
2 年前
查看原帖
RT,一般我们设置的状态是f[i]f[i]表示从iikk的期望,然后发现复杂度太大,于是这篇题解给了一个解决方案;但是这篇题解没有改变ff的状态,而最高赞题解认为f[i]f[i]表示从iii1i-1的期望,如果是这样的话,递推方程还是那个吗?
假设从i+1i+1ii的各个样本分别是(x1,p1),(x2,p2),...(x_1,p_1),(x_2,p_2),...xx表示操作次数,pp表示概率),那么有f[i+1]=xipif[i+1]=\sum x_ip_i;同理设iii1i-1的各个样本分别是(y1,q1),(y2,q2),...(y_1,q_1),(y_2,q_2),...,那么有f[i]=yiqif[i]=\sum y_iq_i;递推公式则有f[i]=in×1+nin×(ij(1+xi+yj)pipj)=in+nin(f[i+1]Pi+f[i]Pi+1+PiPi+1)f[i]=\frac{i}{n}\times 1+\frac{n-i}{n}\times(\underset{i}{\sum}\underset{j}{\sum}(1+x_i+y_j)p_ip_j)=\frac{i}{n}+\frac{n-i}{n}(f[i+1]P_i+f[i]P_{i+1}+P_iP_{i+1}),其中PiP_i表示从iii1i-1的概率
请问一下上述推导有什么问题吗(我概率期望都是自学的qaq可能学假了,请多指教)

回复

1 条回复,欢迎继续交流。

正在加载回复...