Cod sursa(job #701167)

Utilizator algotrollNume Fals algotroll Data 1 martie 2012 14:09:02
Problema Cel mai lung subsir comun Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include<cstdio>
#include<stack>
#define _MAX 1034
using namespace std;
int nA, nB;
int A[_MAX], B[_MAX];
int lcs[_MAX][_MAX];
stack<int > lcs_cont;

int max(int a, int b)
{
    if (a>b) return a;
    else return b;
}

int main()
{
    FILE *f=fopen("cmlsc.in", "r");
    fscanf(f, "%d %d", &nA, &nB);
    for (int i=1;i<=nA;i++)
        fscanf(f,"%d", &A[i]);
    for (int i=1;i<=nB;i++)
        fscanf(f,"%d", &B[i]);
    //solution
    for (int iA=1;iA<=nA;iA++)
        for (int iB=1;iB<=nB;iB++)
            if(A[iA]==B[iB])
            {
                lcs[iA][iB]=lcs[iA-1][iB-1];
                lcs[iA][iB]++;
            }
            else
                lcs[iA][iB]=max(lcs[iA][iB-1], lcs[iA-1][iB]);
    //backtrack
    int curA=nA, curB=nB;
    while(curA>0&&curB>0)
    {
        if (lcs[curA][curB]==lcs[curA-1][curB-1]+1)
        {
            lcs_cont.push(A[curA]);
            curA--; curB--;
        }
        else
            if (lcs[curA-1][curB]>lcs[curA][curB-1])
                curA--;
            else
                curA--;
    }
    //endsolution
    f=fopen("cmlsc.out", "w");
    fprintf(f, "%d\n", lcs[nA][nB]);
    while (!lcs_cont.empty())
    {
        fprintf(f, "%d ", lcs_cont.top());
        lcs_cont.pop();
    }
    return 0;
}