51nod 1670 打怪兽

题目链接

题解：

因此前一轮和后一轮的关系密切，可以使用递推解决。
令$dp[i]$表示第$i$轮依然存活时的方案总数，此时的能量一定是$i$。
显然$dp[0]=n!$，因为，无论怪物怎么排列，第0轮一定是存活的。
我们找到现在能够打败的怪物数量$x$，其中这些怪物已经被打败的是$i$个。
因此，此时我们可以求出第$i+1$轮我依然存活的概率是 x − i n − i \frac {x-i}{n-i} n−ix−i​，只要将这个概率乘上$dp[i]$，我们就能知道$dp[i+1]$的值。
然后期望直接方案数乘上对应的体力值即是答案。

实现细节见代码：

#include 
using namespace std;
typedef long long ll;
const int MAXN = 1e6 + 10;
const int mod = 1e9 + 7;
ll a[MAXN], dp[MAXN];
ll qpow(ll a, ll b) {ll ans = 1;while (b) {if (b & 1) {ans = ans * a % mod;}a = a * a % mod;b >>= 1;}return ans;
}
int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);ll n;cin >> n;for (int i = 0; i < n; i++) {cin >> a[i];}sort(a, a + n);dp[0] = 1;for (int i = 1; i <= n; i++) {dp[0] = dp[0] * i % mod;}ll now = 0;for (ll i = 1; i <= n; i++) {while (i - 1 >= a[now] && now < n) {now++; // 求出当前能够击败的怪物数量}dp[i] = dp[i - 1] * (now - i + 1) % mod * qpow(n - i + 1, mod - 2) % mod; // 递推求出活到第i轮的概率}ll ans = 0;for (ll i = 1; i <= n; i++) {ans = (ans + (dp[i - 1] - dp[i] + mod) % mod * (i - 1) % mod) % mod; // 求期望}ans = (ans + dp[n] * n % mod) % mod;cout << ans << endl;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！