题解

23 条题解

  • 2
    @ 2016-09-18 22:58:40

    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]);
    }
    
  • 0
    @ 2016-06-10 18:38:06

    记录信息
    评测状态 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
    */

  • 0
    @ 2015-04-25 11:24:11

    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.

  • 0
    @ 2014-06-10 15:55:34

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

  • 0
    @ 2010-03-14 20:19:51

    Orz lx

  • 0
    @ 2010-03-14 20:19:10

    历时一星期

    270行

    8KB+

    前后找出Bug10多个

    终于艰难AC。

    不管了,虽然我是管理员

    还是要骂一句

    草尼妈的鸟题

  • 0
    @ 2009-10-24 07:14:24

    oimaster题解太棒了。

    我blog有代码~和注释。供参考。(copy 无意义);

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

  • 0
    @ 2009-07-20 16:17:32

    It seems very difficult.

  • 0
    @ 2009-07-16 22:32:40

    楼下 神牛题解真不错

  • 0
    @ 2009-06-29 18:02:39

    点我看题解

  • 0
    @ 2009-05-28 09:42:21

    SBT维护凸壳。

  • 0
    @ 2009-05-26 15:36:11

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

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

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

  • 0
    @ 2009-05-05 19:57:39

    又是一道水题

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

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

    这道题有若干种方法:

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

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

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

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

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

  • 0
    @ 2009-05-01 14:01:37

    精度没有问题

    用extended就行

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

  • 0
    @ 2009-04-04 20:11:30

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

  • 0
    @ 2009-03-28 22:25:21

    ...vijos比我家电脑快

  • 0
    @ 2009-02-24 20:34:10

    dp不行吗

  • 0
    @ 2009-02-19 12:58:54

    dp可过60%

  • 0
    @ 2009-02-16 19:59:10

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

信息

ID
1508
难度
6
分类
动态规划 | 数据结构 | 平衡树 点击显示
标签
递交数
349
已通过
92
通过率
26%
上传者