[hdu6558][CCPC2018吉林D题]The Moon(期望dp)

当时年少不懂期望$dp$，时隔一年看到这道题感觉好容易....

定义状态$dp[i]$表示当前的$q$值为$i$时的期望，则当$q$值为$100$时$dp[100]=100/q$，这时后发现转移过程中有$1.5$这种小数出现，则把空间变为$1000$,q值也相应扩大$10$倍。

则转移方程为$dp[i]=p/100*(1-q/1000)*dp[min(1000,q+20)]+(1-p/100)*dp[min(1000,q+15)]+1$。

最后的答案为$dp[20]$。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 double dp[];

 int p;

 int main() {

     int t, cnt = ;

     scanf("%d", &t);

     while (t--) {

         scanf("%d", &p);

         dp[] = 100.0 / (p*1.0);

         for (int i = ; i >= ; i--)

             dp[i] = p /  * ( - i / )*dp[min(, i + )] + ( - p / )*dp[min(, i + )] + ;

         printf("Case %d: %.6f\n", cnt++, dp[]);

     }

 }

http [ˌeɪtʃ tiː tiː ˈpiː] 详细X

基本翻译

abbr. 超文本传输协议 (hypertext transport protocol)

网络释义

http: 网站

http Proxy: 代理服务器

http Server: 服务器

巴特西

[hdu6558][CCPC2018吉林D题]The Moon(期望dp)

最新文章

热门文章