cdq分治

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define maxn 100010

using namespace std;
typedef double llg;

struct data{
    llg a,b,k,r,x,y;int id;
    bool operator < (const data &h)const{return k>h.k;}
}s[maxn],ss[maxn];
llg f[maxn];
int n,S[maxn],top;

llg getk(int x,int y){
    if(s[x].x==s[y].x) return 1e100;
    return (s[y].y-s[x].y)/(s[y].x-s[x].x);
}

void solve(int l,int r){
    if(l==r){
        f[l]=max(f[l],f[l-1]);
        s[l].y=f[l]/(s[l].a*s[l].r+s[l].b);
        s[l].x=s[l].y*s[l].r;
        return;
    }
    int mid=l+r>>1,k1=l-1,k2=mid,kk;
    for(int i=l;i<=r;i++)
        if(s[i].id<=mid) ss[++k1]=s[i];
        else ss[++k2]=s[i];
    for(int i=l;i<=r;i++) s[i]=ss[i];
    solve(l,mid); top=0;
    for(int i=l;i<=mid;i++){
        while(top>1 && getk(S[top],i)>=getk(S[top-1],S[top])) top--;
        S[++top]=i;
    }
    for(int i=mid+1,j=1;i<=r;i++){
        while(j<top && getk(S[j],S[j+1])>s[i].k) j++;
        f[s[i].id]=max(f[s[i].id],s[i].a*s[S[j]].x+s[i].b*s[S[j]].y);
    }
    solve(mid+1,r);
    k1=l,k2=mid+1,kk=l-1;
    while(k1<=mid && k2<=r)
        if(s[k1].x<s[k2].x) ss[++kk]=s[k1++];
        else ss[++kk]=s[k2++];
    while(k1<=mid) ss[++kk]=s[k1++];
    while(k2<=r) ss[++kk]=s[k2++];
    for(int i=l;i<=r;i++) s[i]=ss[i];
}

int main(){
    scanf("%d %lf",&n,&f[0]);
    for(int i=1;i<=n;i++){
        scanf("%lf %lf %lf",&s[i].a,&s[i].b,&s[i].r);
        s[i].k=-s[i].a/s[i].b; s[i].id=i;
    }
    sort(s+1,s+n+1); solve(1,n);
    printf("%.3lf",f[n]);
}

记录信息
评测状态 Accepted
题目 P1508 货币兑换
递交时间 2016-06-10 18:37:39
代码语言 C++
评测机 ShadowShore
消耗时间 1467 ms
消耗内存 4864 KiB
评测时间 2016-06-10 18:37:42
评测结果

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 4860 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 4860 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 4860 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 4856 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 4856 KiB, score = 10

测试数据 #5: Accepted, time = 15 ms, mem = 4856 KiB, score = 10

测试数据 #6: Accepted, time = 234 ms, mem = 4860 KiB, score = 10

测试数据 #7: Accepted, time = 203 ms, mem = 4864 KiB, score = 10

测试数据 #8: Accepted, time = 484 ms, mem = 4860 KiB, score = 10

测试数据 #9: Accepted, time = 531 ms, mem = 4860 KiB, score = 10

Accepted, time = 1467 ms, mem = 4864 KiB, score = 100
代码

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const double eps=1e-8;
const double INF=1e20;
const int maxn=100010;
int ch[maxn][2],fa[maxn],rt,tot,n;
double X[maxn],Y[maxn],lk[maxn],rk[maxn],ans;
double fabs(double x){return (x>0)?x:-x;}
void rtate(int x){
int y=fa[x],g=fa[y],c=ch[y][1]==x;
ch[y][c]=ch[x][c^1];fa[ch[y][c]]=y;
ch[x][c^1]=y;fa[y]=x;fa[x]=g;
if(g)ch[g][ch[g][1]==y]=x;
}

void Splay(int x,int g=0){
for(int y;(y=fa[x])!=g;rtate(x))
if(fa[y]!=g)rtate((ch[fa[y]][1]==y)==(ch[y][1]==x)?y:x);
if(!g)rt=x;
}

double Get_K(int j,int k){
if(fabs(X[j]-X[k])<=eps)return INF;
else return (Y[j]-Y[k])/(X[j]-X[k]);
}

int Get_Prev(){
int p=ch[rt][0],ret=p;
while(p){
if(Get_K(rt,p)+eps>=lk[p])p=ch[p][0];
else ret=p,p=ch[p][1];
}
return ret;
}

int Get_Succ(){
int p=ch[rt][1],ret=p;
while(p){
if(Get_K(p,rt)<=rk[p]+eps)p=ch[p][1];
else ret=p,p=ch[p][0];
}
return ret;
}

void Insert(int &t,int anc,int now){
if (t==0){
t=now;
fa[t]=anc;
return;
}
if (X[now]<=X[t]+eps) Insert(ch[t][0],t,now);
else Insert(ch[t][1],t,now);
}

void Update(int p){
Splay(p);
if(ch[p][0]){
int l=Get_Prev();
Splay(l,p);ch[l][1]=0;
rk[l]=lk[p]=Get_K(p,l);
}
else lk[p]=INF;
if(ch[p][1]){
int r=Get_Succ();
Splay(r,p);ch[r][0]=0;
rk[p]=lk[r]=Get_K(r,p);
}
else rk[p]=-INF;
if(lk[p]<=rk[p]+eps){
rt=ch[p][0];ch[rt][1]=ch[p][1];
fa[ch[rt][1]]=rt;fa[rt]=0;
rk[rt]=lk[ch[rt][1]]=Get_K(ch[rt][1],rt);
}
}

int Get_Pos(double k){
int p=rt;
while(p){
if(lk[p]+eps>=k&&k+eps>=rk[p])break;
if(lk[p]<k+eps)p=ch[p][0];
else p=ch[p][1];
}
return p;
}

void Debug(int p){
if(!p)return;
Debug(ch[p][0]);
printf("<%f >",lk[p]);
Debug(ch[p][1]);
}

double Get_Ans(double a,double b){
int p=Get_Pos(-b/a);
return a*Y[p]+b*X[p];
}

int main(){
double a,b,rate;
scanf("%d%lf",&n,&ans);
for(int i=1;i<=n;i++){
scanf("%lf%lf%lf",&a,&b,&rate);
if(i!=1)ans=max(ans,Get_Ans(a,b));
X[i]=ans/(rate*a+b);
Y[i]=X[i]*rate;
Insert(rt,0,i);
Update(i);
// printf("\n");
// Debug(rt);
// printf("\n");

}
printf("%.3f\n",ans);
return 0;
}

/*
10 100
5.007 5.139 1.44
5.142 5.963 1.39
5.248 5.038 1.06
5.705 5.606 1.07
5.151 5.067 1.86
5.924 5.979 1.88
5.069 5.912 1.28
5.075 5.092 1.77
5.485 5.409 1.28
5.161 5.233 1.63

148.311
*/

http://www.cnblogs.com/JSZX11556/p/5155186.html

cdq分治

const
inf = 1 << 30;
type
sortType = record
i : longint; r,k,a,b : double;
end;
var
top,n,i : longint;
f : array[0..200000] of double;
p,tm : array[1..200000] of record
x,y : double;
end;
d,t : array[0..200000] of sortType;

procedure sort(l,r:longint);
var
i,j : longint; mid : double;
begin
i := l; j := r; mid := d[(l+r) >> 1].k;
repeat
while d[i].k > mid do inc(i);
while mid > d[j].k do dec(j);
if i <= j then
begin
d[0] := d[i]; d[i] := d[j]; d[j] := d[0];
inc(i); dec(j);
end;
until i > j;
if l < j then sort(l,j);
if i < r then sort(i,r);
end;

function mul(i,j,k:longint):double;
begin
mul := (p[j].x-p[i].x)*(p[k].y-p[j].y)-(p[k].x-p[j].x)*(p[j].y-p[i].y);
end;

function getk(i,j:longint):double;
begin
if abs(p[j].x-p[i].x) <= 1e-10 then exit(inf);
getk := (p[j].y-p[i].y)/(p[j].x-p[i].x);
end;

function max(x,y:double):double;
begin
max := x; if y > x then max := y;
end;

procedure solve(l,r:longint);
var
mid,j,k,last,i,s_mid,tmp : longint; m : double;
begin
if l = r then
begin
inc(top);
p[top].y := f[l]/(d[l].a*d[l].r+d[l].b);
p[top].x := d[l].r*p[top].y;
exit;
end;
mid := (l+r) >> 1;
j := l; k := mid+1;
for i := l to r do
if d[i].i <= mid then begin t[j] := d[i]; inc(j); end
else begin t[k] := d[i]; inc(k); end;
for i := l to r do d[i] := t[i];
last := top;

solve(l,mid);

j := last+1;
for i := mid+1 to r do
begin
while (j < top) and (d[i].k < getk(j,j+1)) do inc(j);
f[d[i].i] := max(f[d[i].i],p[j].x*d[i].a + p[j].y*d[i].b);
end;
m := f[l];
for i := l+1 to r do
begin
f[i] := max(f[i],m);
m := max(m,f[i]);
end;
s_mid := top;

solve(mid+1,r);

j := last+1; k := s_mid+1;
for i := last+1 to top do
if (j <= s_mid) and (p[j].x < p[k].x) or (k > top) then
begin
tm[i] := p[j]; inc(j);
end else begin
tm[i] := p[k]; inc(k);
end;
for i := last+1 to top do p[i] := tm[i];
tmp := 1;
for i := last+2 to top do
begin
while (tmp > 1) and (mul(last+tmp-1,last+tmp,i) >= 0) do dec(tmp);
inc(tmp); p[last+tmp] := p[i];
end;
top := tmp+last;
end;

begin
readln(n,f[1]);
for i := 1 to n do
begin
readln(d[i].a,d[i].b,d[i].r);
d[i].i := i; d[i].k := -d[i].a/d[i].b;
end;
sort(1,n);
solve(1,n);
writeln(f[n]:0:3);
end.

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std ;

#define cal( p0 , p1 ) ( ( p0.y - p1.y ) / ( p0.x - p1.x ) )
#define MAXN 101000
#define X( x ) ( ( r[ x ] * f[ x ] ) / ( a[ x ] * r[ x ] + b[ x ] ) )
#define Y( x ) ( f[ x ] / ( a[ x ] * r[ x ] + b[ x ] ) )
#define fun( i , p ) ( a[ i ] * p.x + b[ i ] * p.y )
#define clear( x ) memset( x , 0 , sizeof( x ) )

#define update( t ) S( t ) = S( L( t ) ) + S( R( t ) ) + 1
#define L( t ) left[ t ]
#define R( t ) right[ t ]
#define K( t ) key[ t ]
#define S( t ) size[ t ]

const double inf = 100000000 ;
const double INF = inf * inf ;

struct itype {
double x , y ;
bool operator < ( const itype &a ) const {
return x < a.x ;
}
bool operator == ( const itype &a ) const {
return x == a.x ;
}
bool operator > ( const itype &a ) const {
return x > a.x ;
}
} key[ MAXN ] ;

int left[ MAXN ] , right[ MAXN ] , size[ MAXN ] , V = 0 , roof = 0 ;
double lk[ MAXN ] , rk[ MAXN ] ;

itype make( double x , double y ) {
itype u ;
u.x = x , u.y = y ;
return u ;
}

void Left( int &t ) {
int k = R( t ) ;
R( t ) = L( k ) ; update( t ) ;
L( k ) = t ; update( k ) ;
t = k ;
}

void Right( int &t ) {
int k = L( t ) ;
L( t ) = R( k ) ; update( t ) ;
R( k ) = t ; update( k ) ;
t = k ;
}

void maintain( int &t ) {
if ( S( L( L( t ) ) ) > S( R( t ) ) ) {
Right( t ) ;
maintain( R( t ) ) ; maintain( t ) ;
return ;
}
if ( S( R( L( t ) ) ) > S( R( t ) ) ) {
Left( L( t ) ) ; Right( t ) ;
maintain( L( t ) ) , maintain( R( t ) ) ; maintain( t ) ;
return ;
}
if ( S( R( R( t ) ) ) > S( L( t ) ) ) {
Left( t ) ;
maintain( L( t ) ) ; maintain( t ) ;
return ;
}
if ( S( L( R( t ) ) ) > S( L( t ) ) ) {
Right( R( t ) ) ; Left( t ) ;
maintain( L( t ) ) , maintain( R( t ) ) ; maintain( t ) ;
return ;
}
}

void Insert( itype k , int &t ) {
if ( ! t ) {
t = ++ V ;
S( t ) = 1 , K( t ) = k ;
return ;
}
Insert( k , k < K( t ) ? L( t ) : R( t ) ) ;
update( t ) ; maintain( t ) ;
}

void Delete( itype k , int &t ) {
if ( K( t ) == k ) {
if ( ! L( t ) ) {
t = R( t ) ; return ;
} else if ( ! R( t ) ) {
t = L( t ) ; return ;
} else {
Right( t ) ; Delete( k , R( t ) ) ;
}
} else Delete( k , k < K( t ) ? L( t ) : R( t ) ) ;
update( t ) ; maintain( t ) ;
}

itype Prefix( itype k , int t ) {
if ( ! t ) return make( - INF , - INF ) ;
if ( k > K( t ) ) return max( K( t ) , Prefix( k , R( t ) ) ) ;
return Prefix( k , L( t ) ) ;
}

itype Suffix( itype k , int t ) {
if ( ! t ) return make( INF , INF ) ;
if ( K( t ) > k ) return min( K( t ) , Suffix( k , L( t ) ) ) ;
return Suffix( k , R( t ) ) ;
}

int Find( itype k , int t ) {
if ( ! t ) return 0 ;
if ( k == K( t ) ) return t ;
return Find( k , k < K( t ) ? L( t ) : R( t ) ) ;
}

void Push( itype k ) {
int t = Find( k , roof ) ;
if ( t ) {
if ( K( t ).y >= k.y ) return ;
Delete( K( t ) , roof ) ;
}
itype pre = Prefix( k , roof ) , suff = Suffix( k , roof ) ;
if ( cal( pre , k ) > cal( pre , suff ) ) {
for ( ; pre.y != - INF ; ) {
itype ret = Prefix( pre , roof ) ;
if ( cal( ret , pre ) <= cal( pre , k ) ) {
Delete( pre , roof ) ;
pre = ret ;
} else break ;
}
for ( ; suff.y != - INF ; ) {
itype ret = Suffix( suff , roof ) ;
if ( cal( k , ret ) >= cal( k , suff ) ) {
Delete( suff , roof ) ;
suff = ret ;
} else break ;
}
Insert( k , roof ) ;
lk[ V ] = cal( pre , k ) , rk[ V ] = cal( k , suff ) ;
rk[ Find( pre , roof ) ] = cal( pre , k ) ;
lk[ Find( suff , roof ) ] = cal( k , suff ) ;
}
}

itype Select( double k , int t ) {
if ( K( t ).x == - inf ) return Select( k , R( t ) ) ;
if ( K( t ).x == inf ) return Select( k , L( t ) ) ;
if ( lk[ t ] >= k && k >= rk[ t ] ) return K( t ) ;
if ( rk[ t ] > k ) return Select( k , R( t ) ) ;
if ( lk[ t ] < k ) return Select( k , L( t ) ) ;
}

double a[ MAXN ] , b[ MAXN ] , r[ MAXN ] , f[ MAXN ] , money ;
int n ;

int main( ) {
clear( left ) , clear( right ) , clear( size ) ;
Insert( make( 0 , - INF ) , roof ) , Insert( make( inf , - INF ) , roof ) ;
scanf( "%d%lf" , &n , &money ) ;
for ( int i = 0 ; i ++ < n ; ) scanf( "%lf%lf%lf" , a + i , b + i , r + i ) ;
for ( int i = 0 ; i ++ < n ; ) {
f[ i ] = max( money , f[ i - 1 ] ) ;
if ( i > 1 ) {
itype p = Select( - a[ i ] / b[ i ] , roof ) ;
f[ i ] = max( f[ i ] , fun( i , p ) ) ;
}
Push( make( X( i ) , Y( i ) ) ) ;
}
printf( "%.3f\n" , f[ n ] ) ;
return 0 ;
}

Orz lx

历时一星期

270行

8KB+

前后找出Bug10多个

终于艰难AC。

不管了，虽然我是管理员

还是要骂一句

草尼妈的鸟题

oimaster题解太棒了。

我blog有代码~和注释。供参考。（copy 无意义）；

http://hi.baidu.com/think%5Fexist/blog/item/6fedf3c6d3bef1c139db4990.html

It seems very difficult.

楼下 神牛题解真不错

点我看题解

SBT维护凸壳。

嘛= = 将问题转化为平面上点，固定一斜率求最小截距。

然后一定在凸包上，维护下凸包即可。

凸包还是用卷包裹法来思考简单点。。

又是一道水题

不过要小心，题目中有陷阱

因为这道题本来是dp，但是类型上写的却是高级数据结构

这道题有若干种方法：

1:枚举所有情况 O(k^n),k为一个很大的数,接近于无穷大.

2:搜索,时间复杂度O(2^n)

3:记忆化搜索,时间复杂度O(n^2)

4:由记忆化搜索改进而来的动规,时间复杂度O(n^2)

5:动规加平衡树优化,时间复杂度O(n*logn)

精度没有问题

用extended就行

我想知道大牛们的程序为什么跑得这么快

pascal的话move就可以过。。。。

...vijos比我家电脑快

dp不行吗

dp可过60%

好像是Treap..研究一下吧……