Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <ctime>
- using namespace std;
- int n;
- vector<string> a;
- int maxi = 0;
- vector<int> res;
- vector<bool> used;
- vector<vector<int>> dp(n, vector<int> (n, -1));
- vector<int> ans;
- int mnsize = 1e9;
- clock_t t;
- int solve(string a, string b){
- int mx = 0;
- string x = "";
- for(int i = 0; i < b.size(); ++i){
- x.push_back(b[i]);
- if(x.size() > a.size())
- break;
- if(a.substr(a.size() - x.size(), x.size()) == x)
- mx = x.size();
- }
- return mx;
- }
- void sum(int u){
- int pos = 0;
- int mx = -1;
- bool flag = false;
- for(int v = 0; v < n; ++v){
- if(!used[v] && dp[u][v] > mx){
- pos = v;
- mx = dp[u][v];
- flag = true;
- }
- }
- if(!flag)
- return;
- used[pos] = true;
- maxi += a[pos].size() - dp[u][pos];
- res.push_back(pos);
- sum(pos);
- }
- void rec(int u, int sz, int c){
- clock_t b = clock();
- if (double(b - t)/CLOCKS_PER_SEC > 2) {
- cout << mnsize << endl;
- return;
- }
- if(sz >= mnsize)
- return;
- if(c == n){
- cout << ans.size() << endl;
- ans = res;
- mnsize = sz;
- return;
- }
- for(int v = 0; v < n; ++v){
- if(!used[v]){
- res.push_back(v);
- used[v] = true;
- rec(v, sz + a[v].size() - dp[u][v], c + 1);
- res.pop_back();
- used[v] = false;
- }
- }
- }
- int main() {
- t = clock();
- cin >> n;
- a.resize(n);
- ans.resize(n);
- for(int i = 0; i < n; ++i)
- cin >> a[i];
- dp.resize(n, vector<int>(n));
- for(int i = 0; i < n; ++i){
- for(int j = 0; j < n; ++j){
- if(i != j){
- dp[i][j] = solve(a[i], a[j]);
- }
- }
- }
- int st = 0;
- for(int i = 0; i < n; ++i){
- res.clear();
- res.push_back(i);
- maxi = a[i].size();
- used.assign(n, false);
- used[i] = true;
- sum(i);
- if(maxi < mnsize){
- st = i;
- mnsize = maxi;
- ans = res;
- }
- }
- //cout << ans.size() << endl;
- for(int i = 0; i < n; ++i){
- res.clear();
- res.push_back(i);
- maxi = a[i].size();
- used.assign(n, false);
- used[i] = true;
- rec(i, a[i].size(), 1);
- }
- string s = a[ans[0]];
- for(int i = 1; i < n; ++i){
- string xs = a[ans[i]].substr(dp[ans[i - 1]][ans[i]]);
- s += xs;
- }
- cout << s << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement