ICPC 国内予選2011D そして,いくつになった? AOJ1175
円盤を取り除く順番によって取り除ける最大数が違ってくるので取り除く順番を深さ優先探索で全通り試す。
何も工夫せずにシンプルに解いたらTLEだったので、mapを使って状態を保存しておき同じ状態が訪れたら打ち切るようにしてAC。
#include <bits/stdc++.h> #define chmin(a, b) ((a)=min((a), (b))) #define chmax(a, b) ((a)=max((a), (b))) #define fs first #define sc second #define eb emplace_back using namespace std; typedef long long ll; typedef pair<int, int> P; typedef tuple<int, int, int> T; const ll MOD=1e9+7; const ll INF=1e18; int dx[]={0, 1, 0, -1}; int dy[]={-1, 0, 1, 0}; map<int,int> m; int n,d[30][30],abosum[30],ans; bool abo[30][30],exist[30]; int check(bool tmp[30]){ int ret = 0,bit = 1; for(int i = 1;i <= n;i++){ if(tmp[i] == true){ ret += bit; } bit *= 2; } return ret; } void solve(int tmpans,bool texist[30],int tabosum[30]){ ans = max(ans,tmpans); int bit = check(texist); auto itr = m.find(bit); if(itr != m.end()) return; m[bit] = 1; for(int i = 1;i <= n;i++){ for(int j = i+1;j <= n;j++){ if(texist[i] == false || texist[j] == false)continue; if(tabosum[i] != 0 || tabosum[j] != 0) continue; if(d[i][3] != d[j][3]) continue; texist[i] = false; texist[j] = false; bit = check(texist); auto itr = m.find(bit); texist[i] = true; texist[j] = true; if(itr != m.end()) continue; bool tmpexist[30]; for(int k = 1;k <= n;k++){ tmpexist[k] = texist[k]; if(k == i || k == j) tmpexist[k] = false; } int tmpabosum[30]; for(int k = 1;k <= n;k++){ tmpabosum[k] = tabosum[k]; if( abo[i][k] == true && i < k )tmpabosum[k]--; if( abo[j][k] == true && j < k )tmpabosum[k]--; } solve(tmpans+2,tmpexist,tmpabosum); } } } int main(){ while(true){ cin >> n; if(n == 0)break; ans = 0; m.clear(); for(int i = 1;i <= n;i++){ for(int j = 1;j <= n;j++){ abo[i][j] = false; } } for(int i = 1;i <= n;i++){ exist[i] = true; abosum[i] = 0; for(int j = 0;j < 4;j++){ scanf("%d",&d[i][j]); //cin >> d[i][j]; } } for(int i = 1;i <= n;i++){ for(int j = i+1;j <= n;j++){ if( (d[i][0]-d[j][0])*(d[i][0]-d[j][0]) + (d[i][1]-d[j][1])*(d[i][1]-d[j][1]) < (d[i][2]+d[j][2])*(d[i][2]+d[j][2]) ){ abo[i][j] = true; abo[j][i] = true; abosum[j]++; } } } solve(0,exist,abosum); cout << ans << endl; } }