Pagini recente » Cod sursa (job #2928069) | Cod sursa (job #506431) | Cod sursa (job #2874184) | Cod sursa (job #1799182) | Cod sursa (job #2959890)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
using namespace std;
ifstream in("adn.in");
ofstream out("adn.out");
const int maxn = 20;
//vector <pair <int, int> > v[maxn];
string cuv[maxn];
string cit[maxn];
int dp[maxn][(1 << maxn)];
int tata[maxn][(1 << maxn)];
int cost[maxn][maxn];
bitset <maxn> elimin;
vector <int> sol;
/*
class cmp
{
public:
bool operator() (pair <int, int> a, pair <int, int> b)
{
return a.second > b.second;
}
};
priority_queue <pair <int, int>, vector <pair <int, int> >, cmp> pq;
*/
int suprapune(string a, string b)
{
int n = a.size();
int m = b.size();
for(int poz = 0; poz < n; poz++) /// poz = pozitia de la care incerc sa suprapun
{
bool difera = false;
for(int i = poz; i < n && i - poz < m; i++)
{
if(a[i] != b[i - poz])
{
difera = true;
break;
}
}
if(!difera)
{
if(n - poz >= m) /// atunci b este in interiorul lui a
{
//cerr << a << " " << b << " " << poz << "\n";
return -1;
}
return n - poz;
}
}
return 0;
}
int main()
{
int n;
in >> n;
for(int i = 0; i < n; i++)
in >> cit[i];
for(int i = 0; i < n; i++)
for(int j = i + 1; j < n; j++)
if(cit[i] == cit[j])
elimin[j] = 1;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if(i != j && cit[i] != cit[j] && suprapune(cit[i], cit[j]) == -1)
elimin[j] = 1;
int copien = n;
n = 0;
for(int i = 0; i < copien; i++)
if(elimin[i] == 0)
cuv[n++] = cit[i];
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
cost[i][j] = suprapune(cuv[i], cuv[j]);
for(int i = 0; i < n; i++)
dp[i][(1 << i)] = 0;
/*
for(int i = 0; i < n; i++)
cerr << cuv[i] << "\n";
*/
for(int conf = 0; conf < (1 << n); conf++)
{
for(int i = 0; i < n; i++)
{
if(!(conf & (1 << i)))
continue;
for(int j = 0; j < n; j++)
{
if(conf & (1 << j))
continue;
/// ultimul cuvant a fost i si pun cuvantul j
if(dp[j][conf + (1 << j)] < dp[i][conf] + cost[i][j])
{
tata[j][conf + (1 << j)] = i;
dp[j][conf + (1 << j)] = dp[i][conf] + cost[i][j];
}
}
}
}
int mx = 0;
int act = 0;
for(int i = 0; i < n; i++)
{
if(mx < dp[i][(1 << n) - 1])
{
act = i;
mx = dp[i][(1 << n) - 1];
}
}
int confact = (1 << n) - 1;
while(confact > 0)
{
sol.push_back(act);
int ant = tata[act][confact];
confact = confact - (1 << act);
act = ant;
}
reverse(sol.begin(), sol.end());
/*
for(auto it : sol)
cerr << it << "\n";
for(int i = 0; i < sol.size() - 1; i++)
cerr << sol[i] << " " << sol[i + 1] << " " << cost[sol[i]][sol[i + 1]] << "\n";
*/
out << cuv[sol[0]];
for(int i = 1; i < sol.size(); i++)
for(int j = cost[sol[i - 1]][sol[i]]; j < cuv[sol[i]].size(); j++)
out << cuv[sol[i]][j];
out << "\n";
return 0;
}