読者です 読者をやめる 読者になる 読者になる

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;
}