[CF 464D] World of Darkraft - 2

作法：

首先由期望值的線性的特性可以知道，其實可以看成只有一種裝備，每次打完怪之後只有$\frac{1}{k}$的機率可以讓他有機會升級，剩下則什麼都不變。最後答案就是只有一種裝備的答案再乘以$k$。

記$dp[i][j]$代表打完$i$隻怪之後，裝備等級為$j$時期望賺的錢，那麼計算$dp[i][j]$時要考慮由以下幾種狀態轉移過來：

$dp[i-1][j-1]$，機率$=\frac{1}{kj}$，賺的錢$=j-1$。

$dp[i-1][j]$，機率$=\frac{1}{k(j+1)}$，賺的錢$=x$。其中$x\in [1,j]$。

$dp[i-1][j]$，機率$=\frac{k-1}{k}$，賺的錢$=0$。

但轉移式並沒有那麼顯然。考慮某個進行了$i-1$次操作的過程（例如可能是不變、獲得等級$2$裝備、不變、獲得等級$1$裝備），並且最後裝備等級是$j$，那麼這一連串的操作有一個發生的機率$p$，還有他賺的錢數$c$。因此$dp[i-1][j]$中就會有一項等於$p\cdot c$，並且$dp[i-1][j]$就是所有操作$i-1$次變成等級$j$的方法的$p\cdot c$總和。現在要從$dp[i-1][j]$轉移到$dp[i][j]$，假設轉移的機率為$q$（也就是$\frac{1}{k(j+1)}$），獲得的錢為$x$，那麼就要在$dp[i][j]$中加上$(pq)\cdot (c+x)$，並且$dp[i][j]$一樣是所有可能的方法的(機率*錢數)的總和。因為$pq(c+x)=q(pc)+pqx$，因此把$(p,c)$取遍所有$dp[i-1][j]$中的值時，$q\cdot (pc)$的總和就會是$q\cdot dp[i-1][j]$，$pqx$的總和則因為$p$的總和其實就是「進行$i-1$次操作後等級為$j$的機率」，所以可以改寫成$P[i-1][j]\cdot qx$，其中$P[i][j]$代表進行$i$次操作後等級為$j$的機率，並且$P$的遞迴式蠻顯然的。因此就可以得到這樣的轉移式：
$\displaystyle dp[i][j]=dp[i-1][j-1]\cdot \frac{1}{kj}+P[i-1][[j-1]\cdot \frac{1}{kj}\cdot (j-1)$
$\displaystyle +\sum_{x=1}^{j} (dp[i-1][j]\cdot \frac{1}{k(j+1)}+P[i-1][j]\cdot \frac{1}{k(j+1)}\cdot x)$
$\displaystyle +\frac{k-1}{k}\cdot dp[i-1][j]$
其中這三行分別對應三種轉移過來的狀態，並且第二行的顯然可以化簡成$O(1)$計算的東西。因此我們得到了一個$O(n^2)$的算法。

如同很多需要算機率和期望值的題目一樣，若列出的轉移式為$O(n^2)$的，但數字範圍不允許這種複雜度，那麼就可以考慮把機率值太小的地方直接砍掉不算他。在這題中，注意到經過$n$天之後期望的等級不會太大，因為每次增加$1$的機率會越來越小。如果要算準確的話，當等級$i$時只有$\frac{1}{i+1}$的機率會增加，也就是期望需要$i+1$天才能增加$1$，因此可以列出$2+3+...+(x+1)=n$，其中$x$是期望的等級數。因此期望等級數大約在$\sqrt{2n}$左右，因此就可以考慮把超過$\sqrt{2n}$太多的$dp$值直接當成$0$。所以我們的DP陣列的第二維就只要開$1000$左右就可以了，這樣就得到了$O(n\sqrt{n})$的算法。

這樣傳上去很哀傷的TLE了，後來我加了個「若$dp$值或$P$值太小就直接把他的值變成$0$」就過了，並且自己測跑的時間快了非常多，至於為什麼可以參考這篇，要是之前我沒有看到那篇這題可能就要TLE到死了......

code :

#include<bits/stdc++.h>
#define DB double
using namespace std;
const int K=1000 ;
const DB eps=1e-20 ;
 
DB dp[K],p[K] ;
main()
{
    int n,k ; scanf("%d%d",&n,&k) ;
    p[1]=1 ;
    for(int i=1;i<=n;i++) for(int j=min(i+1,K-1);j>=1;j--)
    {
        int t=j*k ;
        dp[j]=(t+k-1)*dp[j]/(t+k) + p[j]*j/(2*k)
                + (dp[j-1]/t) + p[j-1]*(j-1)/t ;
        p[j]=p[j]*(t+k-1)/(t+k)+p[j-1]/t ;
        if(dp[j]<eps) dp[j]=0 ;
        if(p[j]<eps) p[j]=0 ;
    }
    DB ans=0 ;
    for(int i=0;i<K;i++) ans+=dp[i] ;
    printf("%.10f\n",ans*k) ;
}