题目

{% fold 点击显/隐题目 %}

题解

题目思维比较独特,需要一些数学技巧

如图,设 dp[i] 表示当前计数为 i 的时候结束游戏的期望值
则在状态 i 的时候可以转移到状态 0 和 状态 i+j
计算出当前骰子投出和为 j 的概率为 p[j](dp[0]是投出a,b,c的概率)
则有 dp[i] = dp[0]p[0] + sum{ dp[i+j]p[j] }

然后会发现一个很重要的问题,状态同时向两侧转移
也即无论是从大到小还是从小到大或者其他转移形式,这个式子都不满足无后效性
但是这里可以看出,往小了转移只有 dp[0] 一个状态
可以用数学重新推导一下

{% raw %}$
\begin{align*}
dp[i] &= \sum (dp[i+j] \times p[j]) + dp[0] \times p[0] \
设: dp[i] &= A[i] \times dp[0] + B[i] \
带入原式得: dp[i] &= \sum((A[i+j] \times dp[0] + B[i+j) \times p[j]) + dp[0] \times p[0] \
整理得: dp[i] &=\sum ((p[j]*A[i+j]) + p[0]) \times dp[0]) + \sum(p[j] \times B[i+j]) + 1 \
\
\therefore A[i] &= \sum(p[j] \times A[i+j]) + p[0] \
B[i] &= \sum (p[j] \times B[i+j]) + 1 \
\
且: dp[0] &= \frac{B[0]}{1-A[0]} \
A[i] &= B[i] = 0,i>n
\end{align*}
${% endraw %}

这样只需要预先处理出 p[i] 然后用 O(n) 的时间求出 A[i],B[i] 即可
最后结果就是 B[0]/(1-A[0])

代码

{% fold 点击显/隐代码 %}```cpp One Person Game https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
#include
#include
using namespace std;

#define Log(format, ...) //printf(format, ##VA_ARGS)

const int maxk = 3;
const int maxnum = 20;
const int maxn = 550;

int n, k[maxk], a[maxk];
double A[maxn], B[maxn], p[maxnum];

int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%d%d%d%d%d%d%d", &n, &k[0], &k[1], &k[2], &a[0], &a[1], &a[2]);

    memset(p, 0, sizeof(p));
    for (int i = 1; i <= k[0]; ++i)
        for (int j = 1; j <= k[1]; ++j)
            for (int l = 1; l <= k[2]; ++l) {
                if (i == a[0] && j == a[1] && l == a[2]) {
                    p[0] += 1;
                } else {
                    p[i + j + l] += 1;
                }
            }

    int sum = k[0] * k[1] * k[2];
    for (int i = 0; i < maxnum; ++i) {
        p[i] = p[i] / sum;
        Log("%d %f\n", i, p[i]);
    }

    memset(A, 0, sizeof(A));
    memset(B, 0, sizeof(B));
    for (int i = n; i >= 0; --i) {
        for (int j = 3; j < maxnum; ++j) {
            Log("%d %d %f %f %f\n", i,j, p[j],A[i+j],B[i+j]);
            A[i] += p[j] * A[i + j];
            B[i] += p[j] * B[i + j];
        }
        Log("%d %f %f\n", i, A[i],B[i]);
        A[i] += p[0];
        B[i] += 1;
        Log("%d %f %f\n", i, A[i],B[i]);
    }

    printf("%.15f\n", B[0] / (1 - A[0]));
}
return 0;

}

{% endfold %}