AOJ 1320 City Merger
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1320
AOJ久しぶりに解いた気がします。
dp[S][i] := Sでビットが立ってる単語を使って、最後がiになるように単語をつなげたときの最小値
として配るDPをしました。
ほとんど巡回セールスマン問題と同じ遷移をするのでDP自体はあまり難しくない気がしますが、
ABCDE と C
のようにすっぽりはまるケースだけ場合分けが必要です。
#include <bits/stdc++.h> using namespace std; const int INF = 1e9; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; while(cin >> N && N) { vector<string> city(N); for(auto& x : city) cin >> x; vector<vector<int>> str_comp(N, vector<int>(N, 0)); for(int i : _in(N)) for(int j : _in(N)) if(i != j) { str_comp[i][j] = city[j].size(); for(int len : _in(min(city[i].size(), city[j].size()), 0)) if(city[j].substr(0, len) == city[i].substr(city[i].size() - len, len)) { str_comp[i][j] -= len; break; } if(city[i].size() >= city[j].size()) for(int s : _in(city[i].size() - city[j].size())) if(city[i].substr(s, city[j].size()) == city[j]) { str_comp[i][j] = 0; break; } } vector<vector<int>> dp(1 << N, vector<int>(N, INF)); for(int i : _in(N)) dp[1 << i][i] = city[i].size(); for(int S : _in(1 << N)) for(int i : _in(N)) for(int j : _in(N)) if(!(S & (1 << j))) { if(str_comp[i][j] == 0) dp[S | (1 << j)][i] = min(dp[S | (1 << j)][i], dp[S][i]); else dp[S | (1 << j)][j] = min(dp[S | (1 << j)][j], dp[S][i] + str_comp[i][j]); } int S = (1 << N) - 1; cout << *min_element(dp[S].begin(), dp[S].end()) << endl; } return 0; }