0w1

CFR 8 C. Looking for Order ( Bitmask, DP )

Problem - 8C - Codeforces

題意:
給原點 ( sx, sy ),以及 N 個座標 X, Y。每次至多選兩個座標,依序拜訪完後,回到原點。問最好的路徑,使得路徑長最小。兩個座標的路徑長為歐幾里德距離的平方。

資料規模:
The first line of the input file contains the handbag's coordinates xs, ys. The second line contains number n (1 ≤ n ≤ 24) — the amount of objects the girl has. The following n lines contain the objects' coordinates. All the coordinates do not exceed 100 in absolute value. All the given positions are different. All the numbers are integer.
TL: 4000 ms

解法:
dp[ mask ] : 已完成 mask 的拜訪,此時最小總花費
如果直接選兩個點再進行轉移,會超時。
由於拜訪順序無關,每個點又必須被使用,所以每次轉移的時候,第一個選取的座標就固定為還沒有拜訪的座標裡下標最小的。這麼一來轉移就只需要 O( N )。

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

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

template< class T1, class T2 >
int upmin( T1 &x, T2 v ){
  if( x <= v ) return 0;
  x = v; return 1;
}

int sqr( int x ){
  return x * x;
}

signed main(){
  ios::sync_with_stdio( 0 );
  int sx, sy; cin >> sx >> sy;
  int n; cin >> n;
  vector< int > x( n ), y( n );
  for( int i = 0; i < n; ++i ){
    cin >> x[ i ] >> y[ i ];
    x[ i ] -= sx;
    y[ i ] -= sy;
  }
  vector< int > dp( 1 << n, 0x3f3f3f3f );
  vector< int > pre( 1 << n );
  dp[ 0 ] = 0;
  for( int s = 0; s < 1 << n; ++s ){
    int i = __builtin_ctz( ~s );
    if( upmin( dp[ s | 1 << i ], dp[ s ] + 2 * ( sqr( x[ i ] ) + sqr( y[ i ] ) ) ) ){
      pre[ s | 1 << i ] = s;
    }
    for( int j = 0; j < n; ++j ){
      if( i == j ) continue;
      if( s >> j & 1 ) continue;
      if( upmin( dp[ s | 1 << i | 1 << j ], dp[ s ] + sqr( x[ i ] ) + sqr( y[ i ] )
                                  + sqr( x[ i ] - x[ j ] ) + sqr( y[ i ] - y[ j ] )
                                  + sqr( x[ j ] ) + sqr( y[ j ] ) ) ){
        pre[ s | 1 << i | 1 << j ] = s;
      }
    }
  }
  cout << dp[ ( 1 << n ) - 1 ] << endl;
  vector< int > ans = { 0 };
  for( int s = ( 1 << n ) - 1; s; s = pre[ s ] ){
    int ps = pre[ s ];
    vector< int > dc;
    for( int i = 0; i < n; ++i ){
      if( ( s >> i & 1 ) != ( ps >> i & 1 ) ){
        dc.emplace_back( i );
      }
    }
    if( dc.size() == 1 ){
      ans.emplace_back( dc[ 0 ] + 1 );
      ans.emplace_back( 0 );
    } else{
      ans.emplace_back( dc[ 0 ] + 1 );
      ans.emplace_back( dc[ 1 ] + 1 );
      ans.emplace_back( 0 );
    }
  }
  for( int i = ans.size() - 1; i >= 0; --i ){
    cout << ans[ i ] << " \n"[ i == 0 ];
  }
  return 0;
}