# Cod sursa(job #2489381)

Utilizator Data 8 noiembrie 2019 18:39:46 Seif 0 cpp-64 done Arhiva de probleme 2.19 kb
``````#include <bits/stdc++.h>
#define NMAX 1000

using namespace std;

ifstream fin("seif.in");
ofstream fout("seif.out");

int t, k, dp[NMAX + 5][NMAX + 5], nextX[NMAX + 5][30], nextY[NMAX + 5][30];
string x, y;

void Init()
{
for (int i = 1; i <= NMAX; ++i)
for (int j = 1; j <= NMAX; ++j)
dp[i][j] = 0;
for (char ch = 'Z'; ch >= 'A'; --ch)
{
nextX[x.size() + 1][ch] = -1;
nextY[y.size() + 1][ch] = -1;
for (int i = x.size(); i >= 1; --i)
{
if (x[i - 1] == ch)
{
nextX[i][ch - 'A'] = i;
}
else
{
nextX[i][ch - 'A'] = nextX[i + 1][ch - 'A'];
}
}
for (int i = y.size(); i >= 1; --i)
{
if (y[i - 1] == ch)
{
nextY[i][ch - 'A'] = i;
}
else
{
nextY[i][ch - 'A'] = nextY[i + 1][ch - 'A'];
}
}
}
}

void Dinamica()
{
for (int i = x.size(); i >= 1; --i)
{
for (int j = y.size(); j >= 1; --j)
{
if (x[i - 1] == y[j - 1])
{
dp[i][j] = 1 + dp[i + 1][j + 1];
}
else
{
dp[i][j] = max(dp[i + 1][j], dp[i][j + 1]);
}
}
}
}

void GetSolution()
{
bool gata = false;
int p1 = 1, p2 = 1;
int contor = 0;
while (gata == false)
{
gata = true;
for (char ch = 'Z'; ch >= 'A'; --ch)
{
int pos1 = nextX[p1][ch - 'A'];
int pos2 = nextY[p2][ch - 'A'];
if (dp[pos1][pos2] >= k - contor)
{
++contor;
fout << ch;
gata = false;
p1 = pos1 + 1;
p2 = pos2 + 1;
break;
}
}
}
fout << "\n";
}

int main()
{
fin >> t;
while (t--)
{
fin >> k;
fin >> x;
fin >> y;
Init();
Dinamica();
GetSolution();
}
fin.close();
fout.close();
return 0;
}
``````