「NOI2007」 货币兑换

题目链接

问题分析

首先$60$分的DP比较容易。
$$
F_i=max\{F_{i-1},F_j\times\frac{A_iRate_j+B_i}{A_jRate_j+B_j}(1\leqslant j < i)\}
$$
然后考虑如何优化。

我们发现,如果最终
$$
F_i=F_j\times\frac{A_iRate_j+B_i}{A_jRate_j+B_j}
$$
那么可以化成
$$
\frac{F_i}{B_i}=\frac{F_jRate_j}{A_jRate_j+B_j}\times\frac{A_i}{B_i}+\frac{F_j}{A_jRate_j+B_j}
$$
这是个$y=kx+b$的形式。我们不妨令
$$
k_j=\frac{F_jRate_j}{A_jRate_j+B_j}\\
b_j=\frac{F_j}{A_jRate_j+B_j}
$$
而如果从$i$转移到$t$优于从$j$转移到$t$,那么就有
$$
k_i\frac{A_t}{B_t}+b_i=k_j\frac{A_t}{B_t}+b_j
$$

$$
-\frac{A_t}{B_t}<\frac{b_i-b_j}{k_i-k_j}\,\,\,\,(k_i>k_j)
$$

那么就可以斜率优化了。具体的解释可以看程序的注释。

参考程序

#include <cstdio>
#include <cmath>
#include <algorithm>

const int Maxn = 100010;
const double Eps = 1e-9;
struct node {
    double A, B, Rate, k, b, s;
    int Id;
};//k,b的意义如问题分析中所讲,s=-A/B
node Node[ Maxn ], Temp[ Maxn ];
double F[ Maxn ];
int N;
int Stack[ Maxn ], Size;

bool Cmp( node x, node y ) {
    return x.s > y.s;
    //注意不要写x.s+Eps>y.s。这样可能会导致std::sort爆RE。或者可以写成!(x.s<y.s+Eps)
}

double Sl( int a, int b ) {//返回斜率
    if( fabs( Node[ a ].k - Node[ b ].k ) < Eps ) return 1e20;//第6、7个点卡精度需求
    return ( Node[ b ].b - Node[ a ].b ) / ( Node[ b ].k - Node[ a ].k );
}

void Work( int Left, int Right ) {
    if( Left == Right ) {//如果只有一个数,那么就可以直接运算。同时确定k和b
        F[ Left ] = std::max( F[ Left ], F[ Left - 1 ] );
        Node[ Left ].b = F[ Left ] / ( Node[ Left ].A * Node[ Left ].Rate + Node[ Left ].B );
        Node[ Left ].k = Node[ Left ].b * Node[ Left ].Rate;
        return;
    }
    int Mid = ( Left + Right ) >> 1;
    int T1 = Left, T2 = Mid + 1;
    for( int i = Left; i <= Right; ++i )//按时间分治,分成前后两部分
        if( Node[ i ].Id <= Mid ) 
            Temp[ T1++ ] = Node[ i ];
        else 
            Temp[ T2++ ] = Node[ i ];
    for( int i = Left; i <= Right; ++i )
        Node[ i ] = Temp[ i ];
    Work( Left, Mid );//先求出左边
    Size = 0;
    for( int i = Left; i <= Mid; ++i ) {
        while( Size > 1 && Sl( Stack[ Size - 1 ], Stack[ Size ] ) < Sl( Stack[ Size - 1 ], i ) + Eps ) --Size;
        Stack[ ++Size ] = i;
    }//维护一个上凸的凸包
    int T = 1;
    for( int i = Mid + 1; i <= Right; ++i ) {
        while( T < Size && Sl( Stack[ T ], Stack[ T + 1 ] ) + Eps > Node[ i ].s ) ++T;
        F[ Node[ i ].Id ] = std::max( F[ Node[ i ].Id ], Node[ i ].B * ( -Node[ Stack[ T ] ].k * Node[ i ].s + Node[ Stack[ T ] ].b ) );
    }//用左边的答案来更新右边的答案
    Work( Mid + 1, Right );//然后继续求右边
    T = T1 = Left; T2 = Mid + 1;
    while( T1 <= Mid && T2 <= Right ) {//最后按照k的顺序归并,保证k递增
        if( Node[ T1 ].k < Node[ T2 ].k || fabs( Node[ T1 ].k - Node[ T2 ].k ) < Eps && Node[ T1 ].b < Node[ T2 ].b )
            Temp[ T++ ] = Node[ T1++ ];
        else
            Temp[ T++ ] = Node[ T2++ ];
    }
    while( T1 <= Mid )
        Temp[ T++ ] = Node[ T1++ ];
    while( T2 <= Right ) 
        Temp[ T++ ] = Node[ T2++ ];
    for( int i = Left; i <= Right; ++i )
        Node[ i ] = Temp[ i ];
    return;
}

int main() {
    scanf( "%d%lf", &N, &F[ 1 ] );
    for( int i = 1; i <= N; ++i )
        scanf( "%lf%lf%lf", &Node[ i ].A, &Node[ i ].B, &Node[ i ].Rate );
    for( int i = 1; i <= N; ++i ) {
        Node[ i ].s = -Node[ i ].A / Node[ i ].B;
        Node[ i ].Id = i;
    }
    std::sort( Node + 1, Node + N + 1, Cmp );//首先按s排序,保证CDQ分治时s是降序的。
    Work( 1, N );
    printf( "%.3lf\n", F[ N ] );
    return 0;
}

  Reprint please specify: chy's blog 「NOI2007」 货币兑换

 Previous
CF605C Freelancer's Dreams CF605C Freelancer's Dreams
题目链接 解题思路1把这个问题放到平面上。考虑如果总量为$1$能组成哪些$p$和$q$。那么两个点能组成的就是由这两个点为端点的线段。同理,三个点就是三角形,多个点就是这些点的凸包为边界的多边形。 于是我们只需要求经过点$(p,q)$的射线
2019-07-06
Next 
ACG002D - Stamp Rally ACG002D - Stamp Rally
题目链接 题目分析如果对于单个询问,显然我们可以二分答案来做。然后我们就可以整体二分了。 整体二分的思想是这样的: 首先二分一个答案,对于所有询问都判断一遍,然后按照需求分成两部分。之后对于每个部分都进行同样的操作。 对于这道题目,我们
2019-05-13
  TOC