博客


链接



传送门



分析


这道题要注意一定要保证游戏能够买到。如何在最优的情况下保证能够买到游戏，正面考虑太复杂了，我们倒着考虑，创建一个数组f用来记录，从第i开始到最后的最优的期望，对于f[n]也就是最后一天，马上就要停止发售了，所以必须要购买，所以这天的期望是0.5a+0.5b，那么对于一般的情况，例如i，我们已经知道了从i+1天开始购买的最佳的期望f[i+1],如何算出从第i天开始的最佳的期望，如果说，第i天不管购买a还是b都是不如之后购买的期望，那么f[i]=f[i+1],如果说第i天不管购买a还是购买b都是比之后购买要更好，那么肯定不会选择再之后购买，所以最好的期望就是0.5a+0.5b,如果说a<f[i+1]< b的话，这个时候我们为了追求利益最大话，有1/2的概率价格为a，还有1/2概率价格为b，当价格b的时候不如后面买的期望，为了使得期望更小我们选择后面买，

注意价格是每天最早就公布了

，所以我们是知道价格然后进行决策的。此时f[i]=0.5a+0.5f[i+1]。以此类推可以得到第一天决策的最佳期望。


实现


#include <bits/stdc++.h>
#define ll long long
#define ls (u << 1)
#define rs (u << 1 | 1)
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 5;
int a[N], b[N];
double f[N];
void solve() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", a + i);
	for (int i = 1; i <= n; i++) scanf("%d", b + i);
	f[n] = 0.5 * a[n] + 0.5 * b[n];
	for (int i = n - 1; i >= 1; i--) {
		if (min(a[i], b[i]) >= f[i + 1]) f[i] = f[i + 1];
		else if (max(a[i], b[i]) < f[i + 1]) f[i] = 0.5 * a[i] + 0.5 * b[i];
		else f[i] = 0.5 * min(a[i], b[i]) + 0.5 * f[i + 1];
	}
	printf("%lf\n", f[1]);
}
int main(){
//	ios::sync_with_stdio(false);
//	cin.tie(0);
	int T = 1;
	cin >> T;
	while (T--) solve();
	return 0;
}