Pagini recente » Cod sursa (job #700399) | Cod sursa (job #2720193) | Cod sursa (job #440517) | Cod sursa (job #316267) | Cod sursa (job #701172)
Cod sursa(job #701172)
#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
curB--;
}
//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;
}