CodeForces 464D World of Darkraft - 2확률 DP 근사 계산

제목 대의:
현재 월드 오브 다크래프트-2 게임을 하는 사람이 있습니다. 게임에는 k(1<=100)개의 장비 슬롯이 있습니다. 각 장비 슬롯은 초기에 레벨 1의 장비가 있습니다. 지금부터 몬스터를 처치하면 시스템이 장비를 터트리는 규칙은 우선 장비 부위(k개 부위 확률이 같음)를 랜덤으로 정하고 현재 부위에 장착한 장비 레벨이 t이면 해당 부위의 대응 레벨이 [1, t+1]인 장비 하나를 랜덤으로 터트리는 것입니다.현재 유저는 장비가 폭발한 후, 폭발한 장비가 현재 장착한 레벨보다 높으면, 장착한 해당 부위의 장비를 팔고 레벨이 높은 것으로 교환한다. 그렇지 않으면 폭발한 장비를 직접 팔아버리고, 레벨이 i인 장비는 i금화를 판매할 수 있다. n(n<=1e5)마리 몬스터를 처치한 후 획득한 금화 수량에 대한 기대를 물어본다.
대략적인 사고방식:
간단한 확률 DP인데 근사 계산 시 오차 처리를 잘 못하는 것 같아서...
상태 전이 방정식은 코드 주석 부분을 보십시오
코드는 다음과 같습니다.
Result  :  Happy New Year!     Memory  :  16 KB     Time  :  1513 ms

/*
 * Author: Gatevin
 * Created Time:  2015/1/6 14:44:30
 * File Name: Kotomi.cpp
 */
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#include<iomanip>
using namespace std;
const double eps(1e-8);
typedef long long lint;

/*
 *  E(Xi)   i       n             
 *      E(∑Xi) (1 <= i <= k)
 *   k      E(Xi) = E(Xj) 1 <= i != j <= k;
 *   E(∑Xi) = k*E(Xi)
 *        E(Xi)  
 *  E[i][j]     i    ,         j   ,                 
 *   E[i][j] = (1/k)*(∑(E[i + 1][j] + m)/(j + 1) + (E[i + 1][j + 1] + j)/(j + 1)) + (1 - 1/k)*E[i + 1][j];
 *      1 <= m <= j                                                       
 *    E[i][j] = (j/(k*(j + 1)) + (1 - 1/k))*E[i + 1][j] + j/(2*k) + j/(k*(j + 1)) + E[i + 1][j + 1]/(k*(j + 1))
 *    E[n][1 ~ (n + 1)] = 0
 * E[0][1]   ,    n <= 1e5,             
 *   O(n^2)        ,         1e-9   E[0][1]         ,      j > 600  E[i][j]
 *   E[0][1]     ,       ,   O(600*n)      
 */

double E[2][600];

int main()
{
    memset(E, 0, sizeof(E));
    int n, k;
    scanf("%d %d", &n, &k);
    int now = 1;
    for(int i = n - 1; i >= 0; i--)
    {
        now ^= 1;
        for(int j = 1; j < 600; j++)
            E[now][j] = E[now ^ 1][j]*(j*1./(j + 1)/k + (k - 1)*1./k) + (j*1./2 + j*1./(j + 1))/k + 1./(j + 1)*E[now^1][j + 1]/k;
    }
    printf("%.9f
", k*E[now][1]);
    return 0;
}