0w1

ZOJ 3280 Choose The Best ( Bitmask )

ZOJ :: Problems :: Show Problem

題意:
給 N 個 M 維的向量,並給關於每個維度的權值 W。求兩個不同的向量,使得兩個向量在每個維度的差的絕對值乘上對應的權值,總和起來最大。輸出最大總和。

資料規模:
There are no more than 15 cases. Process to the end of file.
For each case, the first line contains two integers n (2 <= n <= 50000) and m (1 <= m <= 8). Then n lines follow and each line contains m integers to specify the n combos. The next line contains m integers means the weights for the nutrients. It is guaranteed that there exist at least two different combos. All weights are positive numbers and no more than 100. All elements in the n m-tuples are positive and no more than 1000.

解法:
先試著考慮只有二維的情況。兩個向量 { xi, yi } 和 { xj, yj } 的貢獻為 wx * abs( xi - xj ) + wy * abs( yi - yj )。考慮絕對值的時候,有一個很常用的手法:abs( xi - xj ) = max( xi - xj, xj - xi )。注意到對於其中任何一維,給其中一個值添上的正負號會和另一個值添上的相反。利用這一點可以發現對於每個向量只要個別枚舉對其 M 維的正負號所有可能。對當前一個 S 表示的正負號排列,當前這個向量套上後,減去其他一樣套上 S 的向量裡總權值最小的,便一定會涵蓋最大權值差。

時機 / 空間複雜度:
O( N * 2^M )

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

signed main(){
  ios::sync_with_stdio( 0 );
  int N, M;
  while( cin >> N >> M ){
    vector< vector< int > > combo( N, vector< int >( M ) );
    for( int i = 0; i < N; ++i ){
      for( int j = 0; j < M; ++j ){
        cin >> combo[ i ][ j ];
      }
    }
    vector< int > wei( M );
    for( int i = 0; i < M; ++i ){
      cin >> wei[ i ];
    }
    int ans = 0;
    vector< int > mask_min( 1 << M, 1 << 28 );
    for( int i = 0; i < N; ++i ){
      for( int j = 0; j < 1 << M; ++j ){
        int sum = 0;
        for( int k = 0; k < M; ++k ){
          if( j >> k & 1 ){
            sum += wei[ k ] * combo[ i ][ k ];
          } else{
            sum -= wei[ k ] * combo[ i ][ k ];
          }
        }
        ans = max( ans, sum - mask_min[ j ] );
        mask_min[ j ] = min( mask_min[ j ], sum );
      }
    }
    cout << ans << endl;
  }
  return 0;
}