D. Babaei and Birthday Cake---cf629D(最长上升子序列和+线段树优化)
2024-09-30 11:58:28
http://codeforces.com/problemset/problem/629/D
题目大意: 我第一反应就是求最长上升子序列和 但是数值太大了 不能直接dp求 可以用线段树优化一下
#include<stdio.h>
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<iostream>
#include<algorithm> using namespace std;
const long long INF = (1LL << );
#define inf 0x3f3f3f3f #define met(a,b) memset(a,b,sizeof(a))
#define N 1005000
const double pi = acos(-1.0);
#define Lson r<<1|1
#define Rson r<<1 double s[N],b[N]; struct node
{
int L,R;
double Max;
int mid()
{
return (L+R)/;
}
}a[N*]; void BuildTree(int r,int L,int R)
{
a[r].L=L;
a[r].R=R;
a[r].Max=;
if(L==R)
return ;
BuildTree(Lson,L,a[r].mid());
BuildTree(Rson,a[r].mid()+,R);
} double Qurry(int r,int L,int R)
{
if(L>R)
return ;
if(a[r].L == L && a[r].R==R)
{
return a[r].Max;
} if(L>a[r].mid())
return Qurry(Rson,L,R);
else if(R<=a[r].mid())
return Qurry(Lson,L,R);
else
{
double m1=Qurry(Lson,L,a[r].mid());
double m2=Qurry(Rson,a[r].mid()+,R);
return max(m1,m2);
}
} void Update(int r,int L,double ans)
{
if(a[r].L==a[r].R && a[r].L==L)
{
a[r].Max=ans;
return;
} if(L>a[r].mid())
Update(Rson,L,ans);
else
Update(Lson,L,ans); a[r].Max=max(a[Lson].Max,a[Rson].Max);
} int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
double r,h;
met(b,);
met(s,);
for(int i=;i<n;i++)
{
scanf("%lf %lf",&r,&h);
s[i]=b[i]=pi*r*r*h;
}
sort(b,b+n);
int len=unique(b,b+n)-b; BuildTree(,,len-); double sum=;
for(int i=;i<n;i++)
{
int pos=lower_bound(b,b+len,s[i])-b;///找到所在的下标
double ans=Qurry(,,pos-)+s[i];///查找之前的最大值
Update(,pos,ans);///更新点
sum=max(sum,ans);
}
printf("%.12lf\n",sum);
}
return ;
}
最新文章
- c#生成静态html文件,封装类
- POJ2456 Aggressive cows
- 窗体==>;>;初始Windows程序
- Xamarin.Android提示找不到mono.Android.Support.v4
- Python 编程规范-----转载
- inno setup详细使用教程
- Session id实现通过Cookie来传输方法及代码参考
- mongodb命令使用
- UVa 10935 - Throwing cards away I (队列问题)
- SQL Server高可用——日志传送(4-2)——部署
- Uva 10780 Again Prime? No Time.(分解质因子)
- 自动化运维工具——puppet详解(二)
- 深度学习(一。深度学习概览)(mooc视频https://www.icourse163.org/learn/MSRA-1002255002?tid=1002370003#/learn/content?type=detail&;id=1003271123)
- warn_alloc():page allocation failure问题分析
- EL表达式jsp页面double小数点后保留两位
- 模拟用户登录(获取cookie/实例化session)
- Linux PWM framework简介和API描述【转】
- Vue:(四)Ajax(Vue-Resource)
- 【hihocoder】 Magic Box
- 【Ubuntu】xrdp完美实现Windows远程访问Ubuntu 16.04