题解 - 帖子 - CQUPT OJ

I. youngmagician想要无伤通关中等题，由于youngmagician一半的骰子各自点数相同，因此可以视为只扔两个骰子，因此答案就转化为了求扔两个m面骰子t次的期望值是多少，使用dp[i] [j]表示第i次扔骰子投掷出j点的期望，易知最后一次投掷出几点就是几点，即dp[t] [i]=i,只有当投掷的点数小于期望时，才会选择继续投掷，因此转移方程为dp[i] [j]=max(j,avg(dp[i+1] [k])),avg为加权平均，由于两个骰子投掷的点数的概率不同，需要手动m^2处理每个点数出现的概率。求出期望后依次与Boss对比大小即可

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll n, m, t, k, q;
ll qmi(ll a, ll k) {  //快速幂 算a的k次方
    ll res = 1;
    while (k) {
        if (k & 1 /*判断是否为奇数 */)
            res = (ll)res * a;
        a = (ll)a * a;
        k >>= 1 /*实际上将K除以2*/;
    }
    return res;
}
ll a[2005000];
ll cnt[2050];
ll sum_cnt[2050];
ll dp0[2050];
int main() {
    // freopen("14.in", "r", stdin);
    // freopen("14.out", "w", stdout);
    cin >> n >> m >> t >> q;
    vector<ll> a(q + 1);
    for (ll x = 1; x <= q; x++) {
        cin >> a[x];
    }
    for (ll x = 1; x <= m; x++) {
        for (ll y = 1; y <= m; y++) {
            cnt[x + y]++;
        }
    }
    double ans = 0;
    double cmp = 0;
    for (ll x = 2; x <= 2 * m; x++) {
        sum_cnt[x] = sum_cnt[x - 1] + cnt[x];
        cmp += x * cnt[x];
        dp0[x] = dp0[x - 1] + x * cnt[x];
    }
    cmp /= m * m;
    ll kcnt = 0;
    for (ll x = t - 1; x >= 1; x--) {
        kcnt = cmp;
        cmp = (sum_cnt[kcnt]) * 1.0 * cmp + dp0[2 * m] - dp0[kcnt];
        cmp /= m * m;
    }
    ans = cmp * n / 2;
    ll res = 0;
    for (ll x = 1; x <= q; x++) {
        if (ans >= a[x]) {
            res++;
        } else {
            break;
        }
    }
    cout << res << "\n";
    return 0;
}