P5242 [USACO19FEB]Cow Dating

- 日理万妓 2021-12-20 07:33 148阅读 0赞

# [题目链接][Link 1] #

# 题意分析 #

首先我们可以得出计算公式

\\\[s\_i=\\prod\_\{k=1\}^i(1-p\_k)\\\]

\\\[f\_i=\\sum\_\{k=1\}^i\\frac\{p\_k\}\{1-p\_k\}\\\]

那么

\\\[ans(i,j)=\\frac\{s\_r\}\{s\_\{l-1\}\}\{f\_r-f\_\{l-1\}\}\\\]

强行枚举 \\(O(n^2)\\)

我们冷机观察一波发现 可以使用**尺取法**

然后优化成了\\(O(n)\\)

# CODE: #

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<cstdlib> #include<string> #include<queue> #include<map> #include<stack> #include<list> #include<set> #include<deque> #include<vector> #include<ctime> #define ll long long #define inf 0x7fffffff #define N 500008 #define IL inline #define M 1008611 #define D long double #define R register using namespace std; template<typename T>IL void read(T &_) { T __=0,___=1;char ____=getchar(); while(!isdigit(____)) {if(____=='-') ___=0;____=getchar();} while(isdigit(____)) {__=(__<<1)+(__<<3)+____-'0';____=getchar();} _=___ ? __:-__; } /*-------------OI使我快乐-------------*/ int n; D num[M],cdy=1.0,wzy,ans; int main() { // freopen(".in","r",stdin); // freopen(".out","w",stdout); read(n); for(R int i=1,x;i<=n;++i) { read(x); num[i]=((D)x/1000000.0); ans=max(ans,num[i]); } for(R int i=1,tail=1;i<=n;++i) { while(tail<=n&&cdy*wzy<cdy*(1.0-num[tail])*(wzy+num[tail]/(1.0-num[tail]))) { cdy*=(1.0-num[tail]); wzy+=num[tail]/(1.0-num[tail]); ++tail; } ans=max(ans,cdy*wzy); cdy/=(1.0-num[i]);wzy-=num[i]/(1.0-num[i]); } printf("%d\n",(int)(ans*1000000)); // fclose(stdin); // fclose(stdout); return 0; }

# *HEOI 2019 RP++* #

转载于:https://www.cnblogs.com/LovToLZX/p/10610015.html

[Link 1]: https://www.luogu.org/problemnew/show/P5242

发表评论取消回复

表情：

评论列表（有 0 条评论，148人围观）

还没有评论，来说两句吧...

相关阅读

相关 P3045 [USACO12FEB]牛券Cow Coupons

洛谷 P3045 \[USACO12FEB\]牛券Cow Coupons [题目描述][Link 1] 一个错误的贪心思路：设优惠券有无数张，然后我们贪心去选，这样就会

系统管理员/ 2023年06月01日 15:00/ 0 赞/ 1 阅读

相关 P1339-[USACO09OCT]热浪Heat Wave

1 include <bits/stdc++.h> 2 define pb push_back 3 define _for(i,a,b) for(i

骑猪看日落/ 2023年06月01日 08:55/ 0 赞/ 8 阅读

相关 P1200 USACO1.1 你的飞碟在这儿

![1686439-20190523082218816-490779599.png][] ![1686439-20190523082325340-632085245.png]

客官°小女子只卖身不卖艺/ 2022年01月07日 16:15/ 0 赞/ 148 阅读

相关 HDU 5242 Game（三个贪心）

Game Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

野性酷女/ 2021年12月24日 17:19/ 0 赞/ 203 阅读

相关 Luogu P2419 [USACO08JAN]牛大赛Cow Contest

传递闭包板子，震惊自己之前居然没学过，特此记录一下。 include <bits/stdc++.h> using namespace std; const int

客官°小女子只卖身不卖艺/ 2021年12月22日 00:49/ 0 赞/ 147 阅读

相关 P5242 [USACO19FEB]Cow Dating

[题目链接][Link 1] 题意分析首先我们可以得出计算公式 \\\[s\_i=\\prod\_\{k=1\}^i(1-p\_k)\\\] \\\[f\_i

- 日理万妓/ 2021年12月20日 07:33/ 0 赞/ 149 阅读

相关 P3009 [USACO11JAN]利润Profits

题目描述 The cows have opened a new business, and Farmer John wants to see how well they

向右看齐/ 2021年11月26日 07:36/ 0 赞/ 225 阅读

相关 [USACO19OPEN]I Would Walk 500 Miles 贪心

题目 [洛谷P5425(点击可跳转)][P5425] 题目描述 Farmer John想要将他的编号为 \\(1 \\ldots N\\)的 N N 头奶牛（ \\

淡淡的烟草味﹌/ 2021年10月19日 04:52/ 0 赞/ 243 阅读

相关 P2944 [USACO09MAR]地震损失2Earthquake Damage 2

题意：确定几个点不割，问最少割几个点使确定的点不能到达T 拆点，每个点 i i i分成 i i i和 i + n i+n i\+n 对于确定不能拆的点， i i i

逃离我推掉我的手/ 2021年09月29日 15:16/ 0 赞/ 325 阅读

相关洛谷 P2947 [USACO09MAR]仰望Look Up

题目描述 Farmer John's N (1 <= N <= 100,000) cows, conveniently numbered 1..N, are once a

谁践踏了优雅/ 2021年09月29日 11:28/ 0 赞/ 285 阅读