AOJ : 1175 - そして，いくつになった？ (And Then. How Many Are There?)

問題概要

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1175&lang=jp
日本語の問題文なので省略します.

アルゴリズム

bitDPで解けます.
それぞれの円盤を取り除いたか, まだ取り除いてないかをビットで管理します.
最大24枚しかないので, この方法で解くことができます.

DPを行うときは, 全ての円盤がある状態から順番に見ていきます.
それぞれの状態において, 消せる2枚の円盤のペアは消して, 全ての遷移パターンを試せばいいです.

あと, AOJでは, メモリ制限があるので, DPの配列をint型で管理してるとMLEしてしまうので気をつけてください.

プログラム

int n; //枚数
int x[25],y[25],r[25],c[25]; //円盤
int b[25]; //各円盤の上に重なっている円盤（ビット管理）

//円盤iと円盤jが重なっているかの判定
bool intersects(int i,int j){
  int dist1 = pow(x[i]-x[j],2) + pow(y[i]-y[j],2);
  int dist2 = pow(r[i]+r[j],2);

  return dist2 > dist1;
}

//DP用
char dp[1<<24];

int main(void){
  while(scanf("%d",&n),n){
    rep(i,n){
      scanf("%d%d%d%d",&x[i],&y[i],&r[i],&c[i]);

      //円盤iの上に重なっている円盤を全て探す
      b[i] = 0;
      rep(j,i) if(intersects(i,j)) b[i] |= (1<<j);
    }

    int ans = 0;
    int to = (1<<n);
    memset(dp,-1,sizeof(dp));
    dp[0] = 0;

    rep(i,to){
      if(dp[i] == -1) continue;

      ans = max(ans,(int)dp[i]);

      //消せる円盤のペア(j,k)を探す
      rep(j,n-1){
        //すでに円盤jは消えている or 円盤jの上の円盤が邪魔して消せない
        if((i & (1<<j)) != 0 || (i & b[j]) != b[j]) continue;

        REP(k,j+1,n){
          //jとkの色が違う or すでに円盤kは消えている or 円盤kの上の円盤が邪魔
          if(c[j] != c[k] || (i & (1<<k)) != 0 || (i & b[k]) != b[k]) continue;

          int next = i | (1<<j) | (1<<k); //next = 円盤jとkを消した状態(ビット管理)
          dp[next] = max((int)dp[next],dp[i]+2);
        }
      }
    }

    printf("%d\n",ans);
  }
}