Java教程

中国地质大学(武汉)第十九届程序设计大赛 - F - 抓住仿生泪滴

本文主要是介绍中国地质大学(武汉)第十九届程序设计大赛 - F - 抓住仿生泪滴,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

传送门


令 \(dp[i]\) 表示前 \(i\) 个人中被鲨死的人数的期望
则有两种情况:

  • $a[i] != 0 $ :那么 \(dp[i] = dp[i - 1]\) 这个人不是仿生泪滴,那么我们不会鲨任何人
  • $a[i] == 0 $ :那么 \(dp[i] = dp[i - 1] + 1 + \frac{i-1-dp[i-1]}{i-1}\) 这个人会和之前的某个人一起被鲨,则可得转移方程
// Problem: 抓住仿生泪滴
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/35753/F
// Memory Limit: 262144 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include  <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define rep(i, a, b) for(int i(a); i <= b; i ++)
#define dec(i, a, b) for(int i(a); i >= b; i --)

#ifdef LOCAL
#include <debugger>
#else
#define debug(...) 42
#endif


template <typename T> inline void chkmax(T &x, T y) { x = max(x, y); }
template <typename T> inline void chkmin(T &x, T y) { x = min(x, y); }

void solve() {
	int n; cin >> n;
	vector<int> a(n);  
	for(int &x: a) cin >> x;
	vector<double> f(n);
	for(int i = 1; i < n; i ++ ) {
		if(a[i]) f[i] = f[i - 1];
		else f[i] = f[i - 1] + 1 + (i - f[i - 1]) / (i);
	}
	cout << f.back();
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << fixed << setprecision(6);
  solve();

  return 0;
}
/*
 *
 *  ┏┓   ┏┓+ +
 * ┏┛┻━━━┛┻┓ + +
 * ┃       ┃
 * ┃   ━   ┃ ++ + + +
 *  ████━████+
 *  ◥██◤ ◥██◤ +
 * ┃   ┻   ┃
 * ┃       ┃ + +
 * ┗━┓   ┏━┛
 *   ┃   ┃ + + + +Code is far away from  
 *   ┃   ┃ + bug with the animal protecting
 *   ┃    ┗━━━┓ 神兽保佑,代码无bug 
 *   ┃        ┣┓
 *    ┃        ┏┛
 *     ┗┓┓┏━┳┓┏┛ + + + +
 *    ┃┫┫ ┃┫┫
 *    ┗┻┛ ┗┻┛+ + + +
 */

这篇关于中国地质大学(武汉)第十九届程序设计大赛 - F - 抓住仿生泪滴的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!