TIOJ 1418 交大都是雷 ( bits DP )

1418 - 交大都是雷 | TIOJ INFOR Online Judge
電人出的題目，本以為又是什麼無聊的優化，可被捏的主要兩個優化都算蠻有梗的（？）。
底而上的寫法第一個就是不要拿不會出現的狀態嘗試更新，因為以這題來說只有以三為倍數的pop_count的狀態才合理。接著就是不必枚舉n^3，因為其中一維可以直接只選定第一個0的位置，這樣並不會少更新狀態。

void solve(){
	int T; cin >> T;
	while( T-- ){
		int N; cin >> N;
		vvi G( N, vi( N ) );
		for( int i = 0; i < N; ++i )
			for( int j = 0; j < N; ++j )
				cin >> G[ i ][ j ];
		vi dp( 1 << N, INF );
		dp[ 0 ] = 0;
		for( int S = 0; S < 1 << N; ++S ) if( dp[ S ] < INF ){
			int i = __builtin_ctz( ~S );	
			for( int j = i + 1; j < N; ++j ) if( not ( S >> j & 1 ) )
				for( int k = j + 1; k < N; ++k ) if( not ( S >> k & 1 ) )
					upmin( dp[ S | 1 << i | 1 << j | 1 << k ], dp[ S ] + G[ i ][ j ] + G[ j ][ k ] + G[ i ][ k ] );
		}
		cout << dp[ ( 1 << N ) - 1 ] << endl;
	}
}