HDU_5781

描述

类似于一个这样的猜数字游戏p。给定一个k，表示数字 p < k, w 表示容许猜错的次数。
你每次猜一个值，若小于等于p，那么用p减去该值。否则给一次警告。
问你让 p 减为 0 的数学期望。

题解

官方题解

解释

因为要求期望，又是二分猜数，所以用max求最大值。
E( i - k , j ) * (i - k + 1) / ( i + 1) 表示猜的k值，不大于存款余额，那么余额只可能是 k + 1 、 k + 2 、…… i + 1。 即 (i - k + 1) / ( i + 1)。因为包括 0 ，所以有 i + 1 个数。
E( k - 1 , j - 1) * k / ( i + 1) 表示猜的k比该数大，被警告了一次，那么余额只可能是0 、 1 、 …… k - 1。即 k / ( i + 1) ，但是由此你可以确定余额小于k。

  • 1 表示走个这一步，期望加一。

c++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <cmath>
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
#define maxn 2005
double dp[maxn][20];
bool visit[maxn][20];
double work(int k,int w){
    if( k == 0)return 0.000000;
    if( w == 0)return 1e12;
    if(visit[k][w])return dp[k][w];
    double tmp=1e12;
    for(int i = 1 ; i <= k ; i++){
        tmp=min(tmp,(k+1-i)*work(k-i,w)/(k+1)+i*work(i-1,w-1)/(k+1)+1);
    }
    visit[k][w] = 1 ;
    return dp[k][w] = tmp;
}
int main(){
    int k,w;
    while(~scanf("%d%d",&k,&w)){
        printf("%.6lf\n",work(k,min(12,w)));
    }
    return 0;
}