Subscribed unsubscribe Subscribe Subscribe

0w1

CFR 799 D. Field expansion ( Dummy Constraints, Greedy )

Problem - D - Codeforces

題意:
你有一個 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;
}