题目
点这里看题目。
分析
首先不难发现答案具有单调性，因此可以二分答案。答案上限为\(V=2m\times \max\{a_i, b_i\}\)。
考虑如何去判断当前的答案。设这个答案为\(mid\)。
我们可以将一块三角形拼图看做一个向量，表示在这个拼图内走过的位移。因此我们的叠放的拼图可以看做一组连续的向量。
因此可以发现拼图摆放顺序不影响结果。
故可以考虑一个 DP :
\(f(i,j,k)\)：前\(i\)块拼图可不可以走到\((j,k)\)这个位置。
转移略。这个做法有着\(O(nm^4)\)的优秀复杂度......
不过判断性的 DP 实际上是非常不划算的。我们考虑把它转成一个最优性的 DP 。
可以发现一个单调性：如果可以用一些拼图走到\((i,j)\)，那么对于\(k\le j\)，我们也一定可以走到\((i,k)\)。
证明不会略，感性理解一下就好（其实不难理解）。
然后就可以想到一个 DP ：
\(f(i,j)\)：\(\max\{k|\text{用前}i\text{块拼图可以走到}(k,j)\}\)。
转移就只需要考虑新的一块拼图放在前\(i-1\)块凑出的边界上的情况：
\[f(i,j)=\max_{\max\{0, j-\lfloor\frac {mid}{a_i}\rfloor\}\le k\le j}\{f(i-1,k)+\lfloor\frac{mid-a_i(j-k)}{b_i}\rfloor\}
\]
\]
转移\(O(nm^2)\)。总时间为\(O(nm^2\log_2 V)\)。
代码
#include <cstdio>
#include <cstring>
const int INF = 0x3f3f3f3f;
const int MAXN = 105, MAXM = 105;
template<typename _T>
void read( _T &x )
{
x = 0;char s = getchar();int f = 1;
while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}
while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}
x *= f;
}
template<typename _T>
void write( _T x )
{
if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }
if( 9 < x ){ write( x / 10 ); }
putchar( x % 10 + '0' );
}
template<typename _T>
_T MAX( const _T a, const _T b )
{
return a > b ? a : b;
}
int f[MAXN][MAXM];
int a[MAXN], b[MAXN];
int N, M;
bool chk( int K )
{
int lA;
memset( f, 0xc0, sizeof f );
f[0][0] = 0;
for( int i = 1 ; i <= N ; i ++ )
for( int j = 0 ; j <= M ; j ++ )
{
lA = 1.0 * K / a[i];
for( int k = j ; ~ k && j - k <= lA ; k -- )
f[i][j] = MAX( f[i][j], f[i - 1][k] + int( 1.0 * K / b[i] + 1.0 * a[i] / b[i] * ( k - j ) ) );
}
return f[N][M] >= M;
}
int main()
{
int l = 1, r = 0, mid;
read( N ), read( M );
for( int i = 1 ; i <= N ; i ++ ) read( a[i] ), read( b[i] ), r = MAX( r, MAX( a[i], b[i] ) );
r *= M << 1;
while( r - l > 1 )
{
mid = l + r >> 1;
if( chk( mid ) ) r = mid;
else l = mid + 1;
}
if( chk( l ) ) write( l );
else write( r );
puts( "" );
return 0;
}