2015年6月19日 星期五

[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) ;
}
 

沒有留言:

張貼留言