这道题目肯定是期望DP，但是稍微分析一下就会发现，对第一个海盗来说，我每次一定是选择当前剩下的宝藏中价值最大的一个最优（所以期望是可以先用上贪心的，以后这里注意）
所以我们先将\(a\)排序，然后依次考虑
第一个海盗先选择，会选择\(a_n\)，然后第二个海盗有\(\frac{1}{n-1}\)的概率分别选择\(a_1,a_2,...,a_{n-1}\)，那么第一个海盗就会有\(\frac{1}{n-1}\)的概率在剩下的\(n-2\)个宝藏中继续选择最大的宝藏，这里就可以构成递推了
我们考虑第一个海盗在有\(i\)个宝藏的情况下，每种宝藏对应的系数是多少。设在有\(i\)个宝藏的时候，第\(j\)小的宝藏对应的系数为\(p_{i,j}\)（比如说当有三个宝藏的时候，第一个海盗的期望收益为\(\frac{1}{2}a_1+\frac{1}{2}a_2+a_3\)，这个手搓一下就行了，那么就有\(p_{3,1}=p_{3,2}=\frac{1}{2},p_{3,3}=1\)）
不难发现递推方程，有\(p_{i,i}=1\)（因为第一个海盗最开始就会选择最大价值的宝藏），$$p_{i,j}=\frac{(j-1)p_{i-2,j-1}+(i-1-j)p_{i-2,j}}{i-1}$$，其中\(j=1,2,...,i-1\)，这个方程可以推导一下
然后提醒一个点，这里没有必要再去推导第二个海盗的期望了，其实感性理解一下，有宝藏总价值等于两个海盗的期望之和
然后官方题解并没有看的很懂。。
标签：选择,期望,Pirates,Two,海盗,frac,宝藏,第一个 From： https://www.cnblogs.com/dingxingdi/p/18100589