问题分析
首先$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;
}