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;
}