c++算法求助（魔法操作：石子游戏）

LSC33

小明和小亮在玩一个石子游戏。

刚开始，小明有n堆石子，小亮有m堆石子。且两人每一堆石子所包含的石子个数均不超过6。

现在，小明需要执行d次魔法操作。每次魔法操作会从当前还剩余的几堆石子中随机选择一堆（选择每一堆的概率相同），并从这一堆中去掉一个石子。

如果某一堆经过一次魔法操作后不再有任何石子，那么在下次魔法操作执行时则不会再考虑这一堆。

现在小明想知道，在经过d次魔法操作之后，小亮一堆石子都不剩的概率是多少？


【输入形式】

输入的第一行包含三个整数n,m和d(1 ≤ n, m ≤ 5; 1 ≤ d ≤ 100)。

接下来一行包含n个整数，表示小明每堆石子的初始石子数。

第三行包含m个整数，表示小亮每堆石子的初始石子数。所有石子数都在1到6之间（包括1和6）。


【输出形式】

输出经过d次魔法操作后，小亮一堆石子都不剩的概率。结果保留四位小数。

kumonagare

whu??

不二猫猫

这是一道概率问题，可以使用动态规划来解决。具体地，设 $f_{i,j,k}$ 表示经过 $k$ 次魔法操作后，小明还剩下 $i$ 堆石子，小亮还剩下 $j$ 堆石子，且小亮的每一堆石子都不剩余的概率。则所求的答案为 $f_{n,m,d}$。

初始时，$f_{i,j,0}=1$，表示还没有进行任何魔法操作，小亮一堆石子都不剩余的概率为1。

接下来考虑如何进行状态转移。每次魔法操作会随机选择一堆石子，并将其中一个石子拿走。因此，对于当前的状态 $f_{i,j,k}$，可以考虑从中选择一堆石子，将其中一个石子拿走，然后转移到下一个状态 $f_{i-1,j,k+1}$ 或 $f_{i,j-1,k+1}$。需要注意的是，如果选择的石子已经没有剩余的石子了，则不能再进行魔法操作。

根据上述状态转移方程，可以使用动态规划求解出所有状态，最终得到 $f_{n,m,d}$ 即可。时间复杂度为 $O(n^3md)$。

以下是 C++ 的代码实现：

#include <iostream>
#include <cstring>
#include <iomanip>
using namespace std;

const int N = 6, M = 105;
double f[N][N][M];
int n, m, d;
int a[N], b[N];

int main()
{
    cin >> n >> m >> d;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) cin >> b[i];
    memset(f, 0, sizeof(f));
    f[n][m][0] = 1;  // 初始状态
    for (int k = 1; k <= d; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                double p = 1.0 / (n + m - k + 1);
                if (a[i] >= k && i <= n) f[i-1][j][k] += f[i][j][k-1] * p;
                if (b[j] >= k && j <= m) f[i][j-1][k] += f[i][j][k-1] * p;
            }
        }
    }
    cout << fixed << setprecision(4) << f[0][0][d] << endl;
    return 0;
}
其中，$p$ 表示随机选择一堆石子的概率，为 $\frac{1}{n+m-k+1}$。为了便于处理，数组下标从 1 开始计算。注意，由于小明和小亮的每一堆石子所包含的石子个数均不超过6，因此可以使用一个 6 维数组来存储状态，但是这样会占用过多的空间，不太实际，因此可以将数组的第三维缩小到 $d+1$。

最后输出的结果需要保留四位小数，可以使用 fixed 和 setprecision 函数来实现。

不二猫猫

不二猫猫 发表于 2023-3-11 17:01

const int N = 6, M = 105;

定义常量 N 和 M，用于表示两个数组 a 和 b 的长度，以及矩阵 f 的维度。

double f[N][N][M];

定义一个三维数组 f，用于记录状态转移方程中的子问题的解。

int n, m, d;

定义三个变量 n、m 和 d，分别表示两个数组 a 和 b 的长度，以及状态转移的最大天数。

int a[N], b[N];

定义两个数组 a 和 b，用于表示两个人对于每天的动作限制。

cin >> n >> m >> d;

从标准输入流中读入三个变量 n、m 和 d。

for (int i = 1; i <= n; i++) cin >> a[i];

从标准输入流中读入数组 a。

for (int i = 1; i <= m; i++) cin >> b[i];

从标准输入流中读入数组 b。

memset(f, 0, sizeof(f));

初始化数组 f 中的所有元素为 0。

f[n][m][0] = 1;

将 f[n][m][0] 的值设置为 1，表示初始状态。

for (int k = 1; k <= d; k++) {

从第 1 天到第 d 天，对每一天进行状态转移。

for (int i = 1; i <= n; i++) {

对数组 a 中的每个元素进行遍历。

for (int j = 1; j <= m; j++) {

对数组 b 中的每个元素进行遍历。

double p = 1.0 / (n + m - k + 1);

计算概率 p，其中 n 和 m 分别表示数组 a 和 b 的长度，k 表示当前天数。

if (a[i] >= k && i <= n) f[i-1][j][k] += f[i][j][k-1] * p;

判断当前天数是否符合数组 a 中第 i 个元素的要求，如果符合，则将 f[i-1][j][k] 的值加上 f[i][j][k-1] * p。

if (b[j] >= k && j <= m) f[i][j-1][k] += f[i][j][k-1] * p;

判断当前天数是否符合数组 b 中第 j 个元素的要求，如果符合，则将 f[i][j-1][k] 的值加上 f[i][j][k-1] * p。

cout << fixed << setprecision(4) << f[0][0][d] << endl;

输出 f[0][0][d] 的值，表示最终状态的解。

总的来说，这段代码的作用是求解一个动态规划问题。该问题的状态转移方程比较简单，主要是根据数组 a 和 b 中的限制条件来计算概率，然后根据概率计算子问题的解。最终，将所有子问题的解进行合并，就可以得到最终的解。

不二猫猫

不二猫猫 发表于 2023-3-11 17:01

const int N = 6, M = 105;

定义常量 N 和 M，用于表示两个数组 a 和 b 的长度，以及矩阵 f 的维度。

double f[N][N][M];

定义一个三维数组 f，用于记录状态转移方程中的子问题的解。

int n, m, d;

定义三个变量 n、m 和 d，分别表示两个数组 a 和 b 的长度，以及状态转移的最大天数。

int a[N], b[N];

定义两个数组 a 和 b，用于表示两个人对于每天的动作限制。

cin >> n >> m >> d;

从标准输入流中读入三个变量 n、m 和 d。

for (int i = 1; i <= n; i++) cin >> a[i];

从标准输入流中读入数组 a。

for (int i = 1; i <= m; i++) cin >> b[i];

从标准输入流中读入数组 b。

memset(f, 0, sizeof(f));

初始化数组 f 中的所有元素为 0。

f[n][m][0] = 1;

将 f[n][m][0] 的值设置为 1，表示初始状态。

for (int k = 1; k <= d; k++) {

从第 1 天到第 d 天，对每一天进行状态转移。

for (int i = 1; i <= n; i++) {

对数组 a 中的每个元素进行遍历。

for (int j = 1; j <= m; j++) {

对数组 b 中的每个元素进行遍历。

double p = 1.0 / (n + m - k + 1);

计算概率 p，其中 n 和 m 分别表示数组 a 和 b 的长度，k 表示当前天数。

if (a[i] >= k && i <= n) f[i-1][j][k] += f[i][j][k-1] * p;

判断当前天数是否符合数组 a 中第 i 个元素的要求，如果符合，则将 f[i-1][j][k] 的值加上 f[i][j][k-1] * p。

if (b[j] >= k && j <= m) f[i][j-1][k] += f[i][j][k-1] * p;

判断当前天数是否符合数组 b 中第 j 个元素的要求，如果符合，则将 f[i][j-1][k] 的值加上 f[i][j][k-1] * p。

cout << fixed << setprecision(4) << f[0][0][d] << endl;

输出 f[0][0][d] 的值，表示最终状态的解。

总的来说，这段代码的作用是求解一个动态规划问题。该问题的状态转移方程比较简单，主要是根据数组 a 和 b 中的限制条件来计算概率，然后根据概率计算子问题的解。最终，将所有子问题的解进行合并，就可以得到最终的解。