aoj1175:And Then. How Many Are There?
解法
円盤の色の種類が高々4種類、それぞれの色について最大の枚数が高々6枚です。よって、円盤の総数は高々24枚です。
したがって、状態数は高々通りしかないことが分かります。
よって、再帰を使って初期状態から状態を遷移させていきます。一度訪れた状態にもう一度訪れることは無駄なので(同じ状態を何度見ても結果は一緒)、一度訪れた状態はメモします。
辿り着けた状態のなかで、取り除かれた円盤の枚数の最大値が答えです。
計算量は、通りの状態に対して、次の状態に遷移するときに回ループを回しているのでくらいです。
初めてACしたときの実行時間が1.62secと少し遅かったので、頑張って定数倍を改善しました(それでも0.99secですが)。
とりあえず1.00secより速くなったのでここで諦めます。
コード
#include<bits/stdc++.h> using namespace std; int n; int x[24],y[24],r[24],c[24]; bool overlap[24][24]; bool memo[1<<24]; bool ok(int a,int bit){ for(int i=0;i<a;i++)if((bit>>i)&1){ if(overlap[a][i])return false; } return true; } int dfs(int bit){ memo[bit]=true; int ret=n; for(int i=0;i<n;i++)if((bit>>i)&1)ret--; for(int i=0;i<n-1;i++){ if(((bit>>i)&1)==0||ok(i,bit)==false)continue; for(int j=i+1;j<n;j++){ if(c[i]!=c[j]||((bit>>j)&1)==0)continue; int to_bit=(bit^(1<<i))^(1<<j); if(ok(j,bit)&&!memo[to_bit]){ ret=max(ret,dfs(to_bit)); } } } return ret; } void solve(){ fill_n(memo,1<<n,false); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ int dist=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]); int sum=(r[i]+r[j])*(r[i]+r[j]); overlap[i][j]=dist<sum; } } cout<<dfs((1<<n)-1)<<endl; } bool input(){ cin>>n; if(!n)return false; for(int i=0;i<n;i++)cin>>x[i]>>y[i]>>r[i]>>c[i]; return true; } int main(){ while(input())solve(); return 0; }