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

POJ 1795 DNA Laboratory

蟻本のビットDPのところの練習問題。
ほとんどAOJ 1320 City Merger - Handmade Summerと同じだけど復元が必要。
1795 -- DNA Laboratory


 最小値を求めるだけなら別に消す必要はないんだけど復元するとき面倒なのですっぽりはまる文字をあらかじめ消してDPします。
 復元は
・到達可能な状態を列挙
・前から、遷移可能かつ到達可能な場合を見て、~個の文字列をくっつけるごとに辞書順最小を見ていく
というのでOK。
 最初は「遷移可能かどうか」が到達可能と同じだと思っていて(自明にぜんぜん違うのになあ…… 悲しい)ハマりました。
 あと出力も明らかに罠ですね。

#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);++i)
#define rep(i,n) REP(i, 0, n)

const int INF = 1e9;
int dp[1 << 15][15];
int comp_s[15][15];
char buf[110];
bool can_reach[1 << 15][15];
bool is_need[15];

string merge(int l, int r, const vector<string>& s) {
    if(l == -1) return s[r];
    int plusLen = comp_s[l][r];
    return s[r].substr(s[r].size() - plusLen, plusLen);
}

const char* solve() {
    int N;
    scanf("%d", &N);
    vector<string> tmp(N);;
    rep(i, N) {
        scanf("%s", buf);
        tmp[i] = string(buf);
    }

    fill_n(is_need, 15, true);
    rep(i, N - 1) REP(j, 1, N)
      if(tmp[i].size() >= tmp[j].size())
        rep(s, tmp[i].size() - tmp[j].size())
          if(tmp[i].substr(s, tmp[j].size()) == tmp[j])
            is_need[j] = false;

    vector<string> s;
    rep(i, N) if(is_need[i]) s.push_back(tmp[i]);
    N = s.size();

    rep(i, N) rep(j, N) if(i != j) {
        int maxlen = min(s[i].size(), s[j].size());
        comp_s[i][j] = s[j].size();
        for(int l = maxlen; l > 0; --l)
          if(s[i].substr(s[i].size() - l, l) == s[j].substr(0, l)) {
              comp_s[i][j] -= l;
              break;
          }
    }
    rep(i, 1 << N) fill_n(dp[i], 15, INF);
    rep(i, N) dp[1 << i][i] = s[i].size();
    
    rep(i, 1 << N) rep(j, N) if(i & (1 << j)) rep(k, N) if(~i & (1 << k)) 
      dp[i | (1 << k)][k] = min(dp[i | (1 << k)][k], dp[i][j] + comp_s[j][k]);
    
    int S = (1 << N) - 1;
    int minLen = *min_element(dp[S], dp[S] + N);

    memset(can_reach, 0, sizeof(can_reach));
    rep(i, N) if(dp[S][i] == minLen) can_reach[S][i] = true;
    for(int i = S; i >= 0; --i)
      rep(j, N) if(i & (1 << j) && can_reach[i][j]) 
        rep(k, N) if(j != k && i & (1 << k)) 
          if(dp[i & ~(1 << j)][k] + comp_s[k][j] == dp[i][j])
            can_reach[i & ~(1 << j)][k] = true;

    int cur_S = 0; int last = -1; string ans = "";
    rep(i, N) {
        string to_comp(1, 'Z' + 1);
        int k = -1;
        rep(j, N) if(~cur_S & (1 << j) && can_reach[cur_S | (1 << j)][j]) {
            bool ok = false;
            if(i == 0 || dp[cur_S][last] + comp_s[last][j] == dp[cur_S | (1 << j)][j])
              ok = true;
            if(!ok) continue;
            string tmp = merge(last, j, s);
            if(to_comp > tmp) {
                to_comp = tmp;
                k = j;
            }
        }
        last = k;
        cur_S |= (1 << last);
        ans += to_comp;
    }
    return ans.c_str();
}

int main() {
    int T; scanf("%d", &T);
    rep(i, T)
      printf("Scenario #%d:\n%s\n\n", i + 1, solve());
    return 0;
}

9WAも出してしまった……。