解題區/解題區 - UVa

UVa 12730 - Skyrk's Bar

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

紳士們上小便的時候，彼此之間會隔著 K 個小便斗 (空著人的小便斗)，請問當有 N 個一排的小便斗，請問壅塞個數的期望值為何 (一次平均可以多少人上小便)。

Sample Input

1
2
3
4
3
4 2
7 2
10 3

Sample Output

1
2
3
Case #1: 1.5000
Case #2: 2.2857
Case #3: 2.4133

Solution

狀態紀錄 dp[i] 表示 i 個一排的小便斗的壅塞期望值。

現在考慮最後一個進入的人所佔的位置 p，則期望值會等於 1 + dp[p-K-1] + dp[i-(p+K)]，分別為左側和右側的期望值，儘管左右兩側狀態也會對邊界有空隙 <= K，但是放入之後與 p 之間空隙最 <= 2K，也塞不下其他人 (至少要 2K + 1)。

由於最後一個人的情況有 i 種，每一種的機率都相同，因此推導結果為 dp[i] = 1 + (dp[1] + dp[2] + ... + dp[i-k-1])/i。

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
27
28
29
30
31
32
33
34
35
36
37
38
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string.h>
#include <assert.h>
using namespace std;
double dp[1048576], sum[1048576];
int main() {
    int testcase, cases = 0;
    int n, m;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n; i++) {
            if (i <= m) {
                dp[i] = 1;
            } else {
                dp[i] = 1 + sum[i - m - 1] * 2.0 / i;
            }
            sum[i] = sum[i - 1] + dp[i];
        }
        printf("Case #%d: %.4lf\n", ++cases, dp[n]);
    }
    return 0;
}
/*
 3
 4 2
 7 2
 10 3
 */