说说当时我的想法 看 n < 1000, 以为是个O(n^2)的dpdp[i] 能从 dp[i+1] 转移过来,然后怎么怎么算,,2333 但是后来发现应该求贡献,把每个位置上的人活下来的期望算出来 然后求和就行了 假设现在1,2,3...n个人都向右跑 对于第i个人来说i+1,i+2,...n都是无影响的.然后考虑i活下来的期望,活下来的情况只有1,2,...i-1没有比i大的,那么第i个人是这些里最大的.也就是说这i个人中最大的那个人的位置是固定的的.那么期望就是 frac{(i-1)!}{i!} = frac{1}{i}; 所以答案就是 \sum_{i=1}{n} = frac{1}{i}; 当时脑抽想的很乱,,233.