はやし屋

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

AOJ1320: City Merger

bitdp
遷移ちがってんのかなあって思ったら、
データが完全に含まれている場合とか見落としていた

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

const int mx = 15*22;

int main(){

  int n ;
  while(cin >> n && n) {

    vector < string > data(n);

    for(int i = 0 ;i < n ; ++i){
      cin >> data[i];
    }
    
    // compress

    vector < string > s; 
    for(int i = 0 ; i < data.size() ; ++i){
      bool can = true;
      for(int j = 0 ; j < data.size() ; ++j){
	if(i == j)continue;
	if(~data[j].find(data[i])){
	  can = false;
	}
      }
      //      cout << " can = " << can << " data = " << data[i] << endl;
      if(can)s.push_back(data[i]);
    }

    n = int(s.size());

    int cost[mx][mx] = {};
    for(int i = 0 ; i < n ; ++i){    
      for(int j = 0 ; j < n ; ++j){  
	if(i == j)continue;
	for(int k = min(s[i].size() ,s[j].size())  ; k >= 0 ; --k){
	  string a = s[i].substr(s[i].size() - k);
	  string b = s[j].substr(0,k);
	  if(a == b){
	    cost[i][j] = k;
	    break;
	  }
	}
      }
    }
    
    
    static int dp[1 << 15][17] ;
    
    for(int i = 0 ; i < 1 << 15 ; ++i){
      for(int j = 0 ; j < 17 ; ++j){
	dp[i][j] = 1 << 28;
      }
    }
    
    for(int i = 0 ; i < n ; ++i){
      dp[1 << i][i] = int(s[i].size());
    }
    
    for(int S = 0 ; S < 1 << n ; ++S){
      for(int i = 0 ; i < n ; ++i){
	if(dp[S][i] != 1 << 28){
	  for(int j = 0 ; j < n ; ++j){
	    if(!((S >> j) & 1)){
	      dp[S | 1 << j][j] = 
		min(dp[S | 1 << j][j] , dp[S][i] + int(s[j].size()) - cost[i][j]);
	    }
	  }
	}
      }
    }
    
    cout << *min_element(dp[(1 << n) - 1], dp[(1 << n) - 1] + 17 ) << endl;
  }
}