CFR 788 C. The Great Mixing ( Math, bitset, DP )

Problem - C - Codeforces

題意：
你的目標濃度是 N / 1000。你有 K 種液體，濃度分別為 a[ i ] / 1000。每一種液體可以用任意非負整數單位容量，求最小正整數，代表使用的總容量成功調配出目標濃度。

資料規模：
The first line contains two integers n, k (0 ≤ n ≤ 1000, 1 ≤ k ≤ 1e6) — carbon dioxide concentration the friends want and the number of Coke types.
The second line contains k integers a1, a2, ..., ak (0 ≤ ai ≤ 1000) — carbon dioxide concentration of each type of Coke. Some Coke types can have same concentration.

解法：
注意 K 依據鴿籠原理，無論多大都可以等價於不超過 1000。
令 x[ i ] : 最優方案下，第 i 種液體的使用容量
列一下數式：



可以發現是個背包問題，要找出滿足上式的最小正整數的

這個問題暴力用位元加速轉移就能過了。
想一下可以發現，對於 ( a[ i ] - N )，只需要檢查 [ -500, 500 ] 範圍的容量即可。有解的情況也不會超過 1000 次轉移。
原因是，考慮任意一組 ( i, j ) 滿足：( a[ i ] - N ) < 0 < ( a[ j ] - N )，顯然可以讓 i 那式子乘上 j 那式子，j 那式子乘上 i 那式子，就得到 0 和，而這花費相當於 - ( a[ i ] - N ) + ( a[ j ] - N ) = a[ j ] - a[ i ]，依據資料範圍，至多只能是 1000。

時間 / 空間複雜度：
O( N^2 * K / 32 ) / O( N )

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000;
const int MAXK = ( int ) 1e6;
const int MAXA = 1000;

int N, K;
int A[ MAXK ];
bitset< 1000 + 1 > dp[ 2 ];

signed main(){
  ios::sync_with_stdio( 0 );
  {
    cin >> N >> K;
    for( int i = 0; i < K; ++i ){
      cin >> A[ i ];
    }
    sort( A, A + K );
    K = unique( A, A + K ) - A;
  }
  {
    int offset = N;
    dp[ 0 ][ offset ] = 1;
    for( int i = 0; i < 1000; ++i ){
      dp[ ~i & 1 ].reset();
      for( int j = 0; j < K; ++j ){
        int t = A[ j ] - N;
        if( t >= 0 ){
          dp[ ~i & 1 ] |= dp[ i & 1 ] << t;
        } else{
          dp[ ~i & 1 ] |= dp[ i & 1 ] >> - t;
        }
      }
      if( dp[ ~i & 1 ][ offset ] ){
        cout << i + 1 << endl;
        exit( 0 );
      }
    }
    cout << -1 << endl;
  }
  return 0;
}