問題文: And Then. How Many Are There? | Aizu Online Judge
盤面の状態数は2^24である。それでDPすれば良い。ただ、AOJではcharじゃないとメモリオーバーになって死ぬ。
実装はDPよりメモ化再帰の方が効率的なのでそうした。
円と円の当たり判定は、
2つの円の中心の距離 < 半径1 + 半径2
が成り立てば当たっている。両辺を2乗してやると、整数で誤差のない当たり判定が実現できる。
追記(07/07):ビットの立ってる本数からいくつ除けたとか逆算できるので、それするとmemoはbool型で良くて、dfsは既にたどり着いた頂点かどうかでreturnするか決めるvoid型の関数で良い。(ansはグローバル変数にして関数内で更新する。)
#include <iostream> #include <cstring> using namespace std; int n; int x[24],y[24],c[24],r[24]; char memo[1<<24]; int hit(int i,int j){ int L = r[i]*r[i] + r[j]*r[j] + 2 * r[i] * r[j]; int X = (x[i]-x[j])*(x[i]-x[j]); int Y = (y[i]-y[j])*(y[i]-y[j]); return X + Y < L; } int nocover(int n,int bit){ for(int i = 0 ; i < n ; i++){ if( (bit>>i&1) && hit(i,n) ) return false; } return true; } int dfs(int bit){ if(~memo[bit]) return memo[bit]; int ans = 0; for(int i = 0 ; i < n ; i++){ for(int j = i+1 ; j < n ; j++){ if( (bit >> j & 1) && (bit >> i & 1) && c[i] == c[j] && nocover(i,bit) && nocover(j,bit) ){ ans = max(ans , dfs( bit & ~(1<<j) & ~(1<<i) ) + 2); } } } return memo[bit] = ans; } int main(){ while(cin >> n , n){ for(int i = 0 ; i < n ; i++){ cin >> x[i] >> y[i] >> r[i] >> c[i]; } memset(memo,-1,sizeof(memo)); cout << dfs((1<<n)-1) << endl; } }