CFR 8 C. Looking for Order ( Bitmask, DP )
題意:
給原點 ( 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; }