Cod sursa(job #2489381)

Utilizator PatrickCplusplusPatrick Ondreovici PatrickCplusplus Data 8 noiembrie 2019 18:39:46
Problema Seif Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 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;
}