Advertisement
deushiro

Untitled

Feb 24th, 2020
279
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.55 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <ctime>
  3. using namespace std;
  4.  
  5.  
  6. int n;
  7. vector<string> a;
  8. int maxi = 0;
  9. vector<int> res;
  10. vector<bool> used;
  11. vector<vector<int>> dp(n, vector<int> (n, -1));
  12. vector<int> ans;
  13. int mnsize = 1e9;
  14. clock_t t;
  15. int solve(string a, string b){
  16.     int mx = 0;
  17.     string x = "";
  18.     for(int i = 0; i < b.size(); ++i){
  19.         x.push_back(b[i]);
  20.         if(x.size() > a.size())
  21.             break;
  22.         if(a.substr(a.size() - x.size(), x.size()) == x)
  23.             mx = x.size();
  24.     }
  25.     return mx;
  26. }
  27.  
  28.  
  29. void sum(int u){
  30.     int pos = 0;
  31.     int mx = -1;
  32.     bool flag = false;
  33.     for(int v = 0; v < n; ++v){
  34.         if(!used[v] && dp[u][v] > mx){
  35.             pos = v;
  36.             mx = dp[u][v];
  37.             flag = true;
  38.         }
  39.     }
  40.     if(!flag)
  41.         return;
  42.     used[pos] = true;
  43.     maxi += a[pos].size() - dp[u][pos];
  44.     res.push_back(pos);
  45.     sum(pos);
  46. }
  47.  
  48.  
  49. void rec(int u, int sz, int c){
  50.     clock_t b = clock();
  51.    
  52.     if (double(b - t)/CLOCKS_PER_SEC > 2) {
  53.         cout << mnsize << endl;
  54.         return;
  55.     }
  56.     if(sz >= mnsize)
  57.         return;
  58.     if(c == n){
  59.         cout << ans.size() << endl;
  60.         ans = res;
  61.         mnsize = sz;
  62.         return;
  63.     }
  64.     for(int v = 0; v < n; ++v){
  65.         if(!used[v]){
  66.             res.push_back(v);
  67.             used[v] = true;
  68.             rec(v, sz + a[v].size() - dp[u][v], c + 1);
  69.             res.pop_back();
  70.             used[v] = false;
  71.         }
  72.     }
  73. }
  74.  
  75. int main() {
  76.     t = clock();
  77.     cin >> n;
  78.     a.resize(n);
  79.     ans.resize(n);
  80.     for(int i = 0; i < n; ++i)
  81.         cin >> a[i];
  82.     dp.resize(n, vector<int>(n));
  83.     for(int i = 0; i < n; ++i){
  84.         for(int j = 0; j < n; ++j){
  85.             if(i != j){
  86.                 dp[i][j] = solve(a[i], a[j]);
  87.             }
  88.         }
  89.     }
  90.     int st = 0;
  91.     for(int i = 0; i < n; ++i){
  92.         res.clear();
  93.         res.push_back(i);
  94.         maxi = a[i].size();
  95.         used.assign(n, false);
  96.         used[i] = true;
  97.         sum(i);
  98.         if(maxi < mnsize){
  99.             st = i;
  100.             mnsize = maxi;
  101.             ans = res;
  102.         }
  103.     }
  104.     //cout << ans.size() << endl;
  105.     for(int i = 0; i < n; ++i){
  106.         res.clear();
  107.         res.push_back(i);
  108.         maxi = a[i].size();
  109.         used.assign(n, false);
  110.         used[i] = true;
  111.         rec(i, a[i].size(), 1);
  112.     }
  113.     string s = a[ans[0]];
  114.     for(int i = 1; i < n; ++i){
  115.         string xs = a[ans[i]].substr(dp[ans[i - 1]][ans[i]]);
  116.         s += xs;
  117.     }
  118.     cout << s << endl;
  119. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement