[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]$。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 double dp[1100];
 5 int p;
 6 int main() {
 7     int t, cnt = 1;
 8     scanf("%d", &t);
 9     while (t--) {
10         scanf("%d", &p);
11         dp[1000] = 100.0 / (p*1.0);
12         for (int i = 1000; i >= 20; i--)
13             dp[i] = p / 100 * (1 - i / 1000)*dp[min(1000, i + 20)] + (1 - p / 100)*dp[min(1000, i + 15)] + 1;
14         printf("Case %d: %.6f
", cnt++, dp[20]);
15     }
16 }

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

基本翻译

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

网络释义

http: 网站

http Proxy: 代理服务器

http Server: 服务器