某DP题目5

题意

　　一个游戏里有k种装备，一开始等级为1，每打败一个怪兽，会随机掉落一件一种类型的装备，它的等级为[1,t+1]中的随机一个数，t为当前佩戴的类型的装备的等级，若掉落t+1等级的装备，就会佩戴该装备，否则不换，然后卖掉不要的装备，卖掉等级为i的装备（任意类型）得到金币i。问打n次怪兽之后的期望金币数。 n <= 100000，k <= 100

分析

　　根据期望的线性性，k是没什么用的，我们可以划分为k个子问题，最后再乘上k就可以了。

　　设F[i][j]表示打了i只怪兽，当前装备等级为j时的概率，分类讨论。

　　捡到的装备是当前类型的，乘上1/k

　　　　1、打完i-1只怪兽时装备等级是j，即F[i-1][j]*j/(j+1)

　　　　2、打完i-1只怪兽时装备等级是j-1，即F[i-1][j-1]/j

　　捡到的不是当前类型的，即打完第i-1只怪兽时等级是j，即F[i-1][j]*k/(k+1)

　　综上：F[i][j] = (1/k)*(F[i-1][j]*j/(j+1)+F[i-1][j-1]/j)+(k/k+1)*F[i-1][j];

　　但是上面这个只是算概率的，要如何计算期望呢?

　　我们很容易发现，你只有打怪物才会掉装备，才能卖钱，因此可以在转移的时候叠加就好了

　　转移到i的状态都来自上一层，我们就以上一层的状态打怪兽来计算即可，当然也是计算当前类型的，即累加(1/k)*F[i-1][j]*(j/2+j/(j+1))

　　j/2怎么推出来的呢，你有1/(j+1)的概率掉1~j等级的装备，那么根据等差数列公式：(j+1)*j/2/(j+1) = j/2，而j/(j+1)的话就是得到了j+1等级的新装备，去卖掉旧的装备。

　 由于精度问题，强制做100次就够了。　

程序

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <string>

 #include <algorithm>

 #include <iostream>

 using namespace std;

 const int maxn = ;

 int n, k;

 double f[][maxn];

 int main()

 {

     freopen("a.in", "r", stdin);

     freopen("a.out", "w", stdout);

     scanf("%d %d", &n, &k);

     for (int i = ; i <= n+; ++i)

         f[][i] = ;

     f[][] = 1.0;

     double t = 1.0/k, ans = ;

     int z = ;

     for (int i = ; i <= n; ++i, z ^= )

         for (int j = min(, i+); j >= ; --j)

         {

             f[z][j] = t*(f[z^][j]/(j+)*j+f[z^][j-]/j)

                     + t*(k-)*f[z^][j];

             ans += t*f[z^][j]*(0.5*j+double(j)/(j+));

         }

     ans *= double(k);

     printf("%.10lf\n", ans);

     return ;

 }