AOJ 1307 Towns along a Highway
Problem C: Towns along a Highway
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1307
問題概要
街が20個くらいある。
すべての街同士のペアの距離情報が与えられる。
考えられる全ての街の配置を求めよ。
一次元です。
解法
探索
まず、一番長い距離が、一番端の街同士の距離であることは間違えない。
この間に他の街を配置していく。
そのとき、今残ってる距離で一番長いもの、は、
間違えなく、両端の街のどちらかとの距離である。
よって、どちらもためしてやって矛盾しないかやってみる。
そこで今まで配置した街とも矛盾しないか比べる。
つかった距離を記憶する
というふうに探索すると
2^18くらいのオーダーに落ちる。
ソース
#include<iostream> #include<algorithm> #include<vector> #include<set> #define REP(i,b,n) for(int i=b;i<(int)n;i++) #define rep(i,n) REP(i,0,n) #define ALL(C) (C).begin(),(C).end() #define FOR(it,o) for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it) using namespace std; const int D = 401; const int N = 20; int remainD[D]; int n, l; vector<int> NOW; set<vector<int> > S; void solve(int now){ if(now == n-2){ vector<int> TMP = NOW; sort(ALL(TMP)); S.insert(TMP); return; } for(int i = l-1; i> 0; i--){ if(remainD[i] == 0 || remainD[l-i] == 0)continue; //front bool out =false; FOR(it, NOW){ int &tmp = remainD[abs(*it - i)]; tmp--; if(tmp < 0){ out = true; } } if(!out){ NOW.push_back(i); solve(now+1); NOW.pop_back(); } FOR(it, NOW){ int &tmp = remainD[abs(*it - i)]; tmp++; } //back out =false; FOR(it, NOW){ int &tmp = remainD[abs(*it - (l-i))]; tmp--; if(tmp < 0){ out = true; } } if(!out){ NOW.push_back(l-i); solve(now+1); NOW.pop_back(); } FOR(it, NOW){ int &tmp = remainD[abs(*it - (l - i))]; tmp++; } break; } } int main(){ while(cin >> n ){ if(n == 0)break; rep(i, D)remainD[i] = 0; rep(i, n*(n-1)/2){ int t; cin >> t; if( i == 0 )l = t; else remainD[t]++; } NOW.clear(); NOW.push_back(0); NOW.push_back(l); S.clear(); solve(0); FOR(it, S){ rep(i, it->size()-1){ if(i != 0)cout << ' ' ; cout << (*it)[i+1] - (*it)[i]; } cout << endl; } cout<< "-----" << endl; } return 0; }