P5242 [USACO19FEB]Cow Dating

- 日理万妓 2021-12-20 07:33 179阅读 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 条评论，179人围观）

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

相关阅读

相关 P19 JToolBar工具栏

P19 JToolBar工具栏 1.概述 2.代码实例 3.效果演示 > 系统：Win10 > Java：1.8.0\_333 > IDEA：

ゞ浴缸里的玫瑰/ 2024年04月07日 15:41/ 0 赞/ 84 阅读

相关 P3045 [USACO12FEB]牛券Cow Coupons

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

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

相关 P3119-[USACO15JAN]草鉴定Grass Cownoisseur

1 include <iostream> 2 include <vector> 3 include <queue> 4 includ

怼烎@/ 2023年06月01日 08:57/ 0 赞/ 31 阅读

相关 P2746-[USACO5.3]校园网Network of Schools

1 include <bits/stdc++.h> 2 3 using namespace std; 4 define _for(

Dear 丶/ 2023年06月01日 08:57/ 0 赞/ 31 阅读

相关 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 赞/ 32 阅读

相关 [USACO19OPEN]Snakes

题面： > 传说，数千年前圣帕特里克消灭了哞尔兰所有的蛇。然而，蛇们现在卷土重来了！圣帕特里克节是在每年的3月17日，所以Bessie要用彻底清除哞尔兰所有的蛇来纪念圣帕特里

古城微笑少年丶/ 2023年06月01日 06:09/ 0 赞/ 2 阅读

相关 P4377 [USACO18OPEN]Talent Show

这道题可以作为最优比率背包问题的模板题了。好像属于01分数规划。我们这里用二分答案的方法解决。题目要我们求\\(\\frac\{\\sum\{t\}\}\{\\sum\

àì夳堔傛蜴生んèń/ 2021年12月22日 15:56/ 0 赞/ 158 阅读

相关 P5242 [USACO19FEB]Cow Dating

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

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

相关 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 赞/ 256 阅读

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

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

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