はやし屋

競技プログラミングのメモ きたない

AOJ 2022: Princess, a Cryptanalyst

後ろにつなげていくイメージのbitdp
INF足りなくてWAした~~~~~~~~~~~
""でもよかったような

#include<iostream>
#include<algorithm>
using namespace std ;
int n ;

string s[11];
string G[11][11];
string dp[11][1<<11];

const string INF = "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";

string MIN(string a , string b){
  return a.size()==b.size()?min(a,b):a.size()<b.size()?a:b;
}

string solve(int u , int v){
  if(u == (1<<n)-1)return "";
  if(dp[v][u] != INF)return dp[v][u];
  string ret = INF;
  for(int i = 0 ; i < n ; ++i){
    if(!(u&(1<<i)))ret = MIN(ret,G[v][i]+solve(u|1<<i,i));
  }
  return dp[v][u] = ret;
}

int main(){
  while(cin >> n && n){
    for(int i = 0 ; i < n ; ++i)cin >> s[i];

    int u = 0 ;
    for(int i = 0 ; i < 10 ; ++i){
      for(int j = 0 ; j < 1 << 10 ; ++j){
	dp[i][j] = INF;
      }
    }

    for(int i = 0 ; i < n ; ++i){
      for(int j = 0 ; j < n ; ++j){
	if(i == j)continue;
	if(!(u&(1<<j)) && !(u&(1<<i))){
	  if(~s[i].find(s[j])){
	    u |= 1 << j;
	  }
	}
      }
    }

    for(int i = 0 ; i < n ; ++i){
      for(int j = 0 ; j < n ; ++j){
	if(i == j)continue;
	G[i][j] = s[j];
	if(!(u&(1<<j)) && !(u&(1<<i))){
	  for(int k = 0 ; k < s[i].size() ; ++k){
	    string cut = s[i].substr(k);
	    int Idx = s[j].find(cut);
	    if(Idx == 0){
	      string in = s[j].substr(cut.size());
	      G[i][j] = in;break;
	    }
	  }
	}
      }
    }

    string ret = INF;
    for(int i = 0 ; i < n ; ++i){
      if(!(u&(1<<i)))ret = MIN(ret,s[i]+solve(u|(1<<i),i));
    }
    cout << ret << endl;
  }
  return 0;
}