LightOj_1274 Beating the Dataset
LightOj_1274 Beating the Dataset
题意：
给一个文档， 这个文档由yes 、no 组成， 共有s个byte， 共有n个yes、no。
假设yes的个数为yes_num, no的个数为no_num。
将这n个数进行排列， 对于每个排列， 将其右移一个结果， 并在最左端补上yes， 再将其与原排列进行对比， 看有多少个不同的。
计算所有排列中 不同结果的平均次数。
思路：
可能题意说的不是很清楚， 这里抽象一下， 将yes用1代替， no用0代替。
当n = 3, s = 7时， 也就是2个0 一个1， 有下面三种排列
100, 010, 001
对于每种排列的处理：
100
110 不同的只有一个， 有三种情况， 每种情况抽中的概率是1/3 所以 当前情况的期望就是 1/3 * 1
010
101 不同的有三个， 当前情况的期望是1/3 * 3
001
100 不同的有两个，当前情况的期望是1/3 * 2
so, 总的期望就是1/3 * （1+3+2） = 6 / 3 = 2
将原排列进行整理下， 会发现一个现象。
每种排列的次数就是原排列中有多少个相邻不同的数字， 如果最左端是0， 那么还要 + 1 （因为左端要补上1， 和0 不同 所以要加1）
此时可以发现， 当前状态的期望数其实和上一状态是有关系的。
假设dp[i][j][flag]为当前为第i位， 前面有j个1(yes)， 上一状态（第i + 1 位） 是flag(0 == no, 1 == yes)。
那么， flag 要么为0， 要么为一， 也即 第i + 1位的状态。
{……j 个 yes……} flag k {…………}， k为第i + 2 位的状态。
dp[i][j][flag] = (dp[i+1][j][0] + (flag != 0))* p_no + (dp[i + 1][j + 1] + (flag != 1)) * p_yes.
也有大神推出公式了， 不过在下实在推不出来 囧 坐等大神解答。
公式：（2.0 * yes_num * no_num + no_num）/(yes_num + no_num)
加一段递归代码用以理解状态转移方程。
1 double dp(int n, int y, int a)
2 {
3 if (n == 0) // There are no options to choose
4 return 0;
5 double p_no = (n - y) / (double) n;
6 double p_yes = y / (double) n;
7 double ans = 0;
8 if (y < n)
9 ans += (dp(n - 1, y, 0) + (a != 0)) * p_no;
10 if (y > 0)
11 ans += (dp(n - 1, y - 1, 1) + (a != 1)) * p_yes;
12 return ans;
13 }代码：
1 #include <cmath>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <ctime>
6 #include <set>
7 #include <map>
8 #include <list>
9 #include <queue>
10 #include <string>
11 #include <vector>
12 #include <fstream>
13 #include <iterator>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17 #define LL long long
18 #define INF 0x3f3f3f3f
19 #define MOD 1000000007
20 #define eps 1e-6
21 #define MAXN 5050
22 int n, s;
23 double dp[2][MAXN][2];// 0 --> NO, 1 --> yes
24 int yes_num, no_num;
25 int kcase = 0;
26 void solve()
27 {
28 memset(dp, 0, sizeof(dp));
29 yes_num = s - 2 * n;
30 no_num = n - yes_num;
31 for(int i = 1; i <= n + 1; i ++)
32 for(int j = 0; j <= min(i, yes_num); j ++)
33 {
34 double p_yes = j * 1.0 / i;
35 double p_no = (i - j) * 1.0 / i;
36
37 if(j - 1 >= 0)
38 {
39 dp[i % 2][j][1] = dp[(i + 1) % 2][j - 1][1] * p_yes + (dp[(i + 1) % 2][j][0] + 1.0) * p_no;
40 dp[i % 2][j][0] = (dp[(i + 1) % 2][j - 1][1] + 1.0) * p_yes + dp[(i + 1) % 2][j][0] * p_no;
41 }
42 else
43 {
44 dp[i % 2][j][1] = (dp[(i + 1) % 2][j][0] + 1.0) * p_no;
45 dp[i % 2][j][0] = dp[(i + 1) % 2][j][0] * p_no;
46 }
47 }
48 printf("Case %d: %.7lf\n", ++kcase, dp[n % 2][yes_num][1]);
49 }
50 void solve_()
51 {
52 memset(dp, 0, sizeof(dp));
53 yes_num = s - 2 * n;
54 no_num = n - yes_num;
55
56 for(int i = n - 1; i >= 0; i --)
57 for(int j = min(i, yes_num); j >= 0 && (i - j <= no_num); j --)
58 {
59 double p_yes = (yes_num - j) * 1.0 / (n - i);
60 double p_no = (no_num - (i - j)) * 1.0 / (n - i);
61
62 if(j + 1 <= yes_num)
63 {
64 dp[i % 2][j][0] = (dp[(i + 1) % 2][j + 1][1] + 1.0) * p_yes + dp[(i + 1) % 2][j][0] * p_no;
65 dp[i % 2][j][1] = dp[(i + 1) % 2][j + 1][1] * p_yes + (dp[(i + 1) % 2][j][0] + 1.0) *p_no;
66 }
67 else
68 {
69 dp[i % 2][j][0] = p_yes + dp[(i + 1) % 2][j][0] * p_no;
70 dp[i % 2][j][1] = (dp[(i + 1) % 2][j][0] + 1.0) *p_no;
71 }
72 }
73 printf("Case %d: %.7lf\n", ++kcase, dp[0][0][1]);
74 }
75
76 int main()
77 {
78 int T;
79 scanf("%d", &T);
80 while(T --)
81 {
82 scanf("%d %d", &n, &s);
83 solve_();
84 }
85 return 0;
86 }