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 ;
}

最新文章

  1. c#生成静态html文件,封装类
  2. POJ2456 Aggressive cows
  3. 窗体==&gt;&gt;初始Windows程序
  4. Xamarin.Android提示找不到mono.Android.Support.v4
  5. Python 编程规范-----转载
  6. inno setup详细使用教程
  7. Session id实现通过Cookie来传输方法及代码参考
  8. mongodb命令使用
  9. UVa 10935 - Throwing cards away I (队列问题)
  10. SQL Server高可用——日志传送(4-2)——部署
  11. Uva 10780 Again Prime? No Time.(分解质因子)
  12. 自动化运维工具——puppet详解(二)
  13. 深度学习(一。深度学习概览)(mooc视频https://www.icourse163.org/learn/MSRA-1002255002?tid=1002370003#/learn/content?type=detail&amp;id=1003271123)
  14. warn_alloc():page allocation failure问题分析
  15. EL表达式jsp页面double小数点后保留两位
  16. 模拟用户登录(获取cookie/实例化session)
  17. Linux PWM framework简介和API描述【转】
  18. Vue:(四)Ajax(Vue-Resource)
  19. 【hihocoder】 Magic Box
  20. 【Ubuntu】xrdp完美实现Windows远程访问Ubuntu 16.04

热门文章

  1. ubuntu破解密码方法
  2. javaee 第四周作业
  3. ref版的 摄像头 读取 因为id的时候,id不能重复 还要用时间戳,比较麻烦
  4. Keil Debug (printf) Viewer
  5. delphi中使用自定义资源的方法
  6. 读懂CommonJS的模块加载
  7. mysql5.7zip安装
  8. 【Java IO流】浅谈io,bio,nio,aio
  9. 利用springboot创建多模块项目
  10. vue App.vue router 过渡效果, keep-alive 结合使用示例