CFR 799 D. Field expansion ( Dummy Constraints, Greedy )
題意:
你有一個 H * W 的棋盤。你的目標是要在這之棋盤上能容下 A * B 的棋盤,但是容的時候邊之間必須平行或垂直。你有 N 個放大燈,選長或寬照上去之後那個邊會變 X[ i ] 倍。你可以以任意順序使用放大燈,問至少要用幾個放大燈。無解輸出 -1。
制約:
The first line contains five integers a, b, h, w and n (1 ≤ a, b, h, w, n ≤ 100 000) — the sizes of the rectangle needed to be placed, the initial sizes of the field and the number of available extensions.
The second line contains n integers a1, a2, ..., an (2 ≤ ai ≤ 100 000), where ai equals the integer a side multiplies by when the i-th extension is applied.
解法:
考慮無視 2倍放大燈的存在,那麼至多會想關切最大的 22 個放大燈 ( 3**11 > 1e5 )。那麼直接枚舉所有子集合分配給一邊,這個子集合外的貪心給另一邊,最後不夠的都用 2倍放大燈直接補就可以了。
沒處理到旋轉的部分就過 pretest,慘痛。
大家好像都是用記憶化搜索過的,只考慮最大的 34 個放大燈 ( 2**17 > 1e5 ):
dp[ i ][ j ][ k ]:已考慮前 i 個放大燈,已取 j 個放大燈,長放大 min( 1e5, k ) 倍時,寬最大可以放大多少。
時間 / 空間複雜度:
O( N lg N )
#include <bits/stdc++.h> using namespace std; const int MAXN = int( 1e5 ); int A, B, H, W, N; int X[ MAXN ]; signed main() { ios::sync_with_stdio( 0 ); cin >> A >> B >> H >> W >> N; swap( A, H ); swap( B, W ); for( int i = 0; i < N; ++i ) { cin >> X[ i ]; } sort( X, X + N, greater< int >() ); vector< int > bg2; for( int i = 0; bg2.size() < 22 and i < N and X[ i ] > 2; ++i ) { bg2.emplace_back( X[ i ] ); } int ans = 0x3f3f3f3f; for( int s = 0; s < 1 << bg2.size(); ++s ) { int xx = 1, yy = 1; int cx = __builtin_popcount( s ); int cy = 0; for( int i = 0; i < bg2.size(); ++i ) { if( s >> i & 1 ) { xx = min( 1000000LL, 1LL * xx * bg2[ i ] ); } else { if( 1LL * yy * B < W ) { yy = min( 1000000LL, 1LL * yy * bg2[ i ] ); ++cy; } } } int c2 = N - bg2.size(); while( c2 and 1LL * xx * A < H ) { xx = min( 1000000LL, 2LL * xx ); ++cx; --c2; } while( c2 and 1LL * yy * B < W ) { yy = min( 1000000LL, 2LL * yy ); ++cy; --c2; } if( 1LL * xx * A < H or 1LL * yy * B < W ) continue; ans = min( ans, cx + cy ); } swap( A, B ); for( int s = 0; s < 1 << bg2.size(); ++s ) { int xx = 1, yy = 1; int cx = __builtin_popcount( s ); int cy = 0; for( int i = 0; i < bg2.size(); ++i ) { if( s >> i & 1 ) { xx = min( 1000000LL, 1LL * xx * bg2[ i ] ); } else { if( 1LL * yy * B < W ) { yy = min( 1000000LL, 1LL * yy * bg2[ i ] ); ++cy; } } } int c2 = N - bg2.size(); while( c2 and 1LL * xx * A < H ) { xx = min( 1000000LL, 2LL * xx ); ++cx; --c2; } while( c2 and 1LL * yy * B < W ) { yy = min( 1000000LL, 2LL * yy ); ++cy; --c2; } if( 1LL * xx * A < H or 1LL * yy * B < W ) continue; ans = min( ans, cx + cy ); } if( ans == 0x3f3f3f3f ) { cout << -1 << endl; } else { cout << ans << endl; } return 0; }