题意分析

题目要求计算掷$n$个$m$面骰子后，零花钱钞票数量的期望值。规则为：1）若骰子点数总和$s$大于削减额$k$，则获得$s-k$张钞票；2）若$s \leq k$，则至少获得1张钞票。每个骰子各面概率均等，需计算所有可能情况下的期望值。

解题思路

代码采用动态规划求解：1）用$dp[i][j]$表示掷$i$个骰子得到总和为$j$的方案数；2）初始状态：$dp[1][1 \dots m] = 1$；3）状态转移：$dp[i][j] = \sum_{t=1}^{m} dp[i-1][j-t]$；4）计算期望值：$\frac{\sum_{j=1}^{k} dp[n][j] + \sum_{j=k+1}^{nm} (j-k) \times dp[n][j]}{m^n}$。需注意：1）使用滚动数组优化空间；2）处理大数运算以避免溢出；3）输出保留8位小数。

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<math.h>
using namespace std;

int main()
{
    int n, m, k;
    while (scanf("%d%d%d", &n, &m, &k) != EOF)
    {
        if (n == 0 && m == 0 && k == 0)
            break;
            
        int sum = n * m;
        // 使用动态分配的数组，避免栈溢出
        int **dp = new int*[2];
        dp[0] = new int[sum + 1];
        dp[1] = new int[sum + 1];
        
        // 初始化数组
        for (int i = 0; i <= sum; i++)
        {
            dp[0][i] = 0;
            dp[1][i] = 0;
        }
        
        // 基础情况：一个骰子的情况
        for (int i = 1; i <= m; i++)
            dp[1][i] = 1;
        
        // 动态规划计算多个骰子的情况
        for (int i = 2; i <= n; i++)
        {
            for (int j = 0; j <= sum; j++)
                dp[i % 2][j] = 0;
                
            for (int x = 1; x <= sum; x++)
            {
                for (int j = 1; j <= m && j <= x; j++)
                    dp[i % 2][x] += dp[1 - i % 2][x - j];
            }
        }
        
        // 计算期望值
        double all = pow((double)m, (double)n);
        double ans = 0.0;
        
        // 当总和不超过k时，得到1张钞票
        for (int i = 1; i <= k; i++)
            ans += (double)dp[n % 2][i];
            
        // 当总和超过k时，得到sum-k张钞票
        for (int i = k + 1; i <= sum; i++)
            ans += (double)(i - k) * dp[n % 2][i];
            
        printf("%.8lf\n", ans / all);
        
        // 释放动态分配的内存
        delete[] dp[0];
        delete[] dp[1];
        delete[] dp;
    }
    return 0;
}