T1.3 Dãy chung dài nhất của hai dãy số

Cho hai số nguyên dương M, N (0<M,N<100) và hai dãy số nguyên a1, a2,...,an và b1,b2,...,bm. Tìm một dãy dài nhất C nhận được từ A bằng cách xoá đi một số số hạng và cũng nhận được từ B bằng cách xoá đi một số số hạng (nói chung không cùng chỉ số với dãy A). Ta gọi C là dãy con chung dài nhất của hai dãy A và B.
Dữ liệu vào từ file SUBST.INP
 Dòng 1 ghi số nguyên dương N, M.
 Dòng 2 chứa n số a1, a2,..., an
 Dòng 3 chứa m số b1,b2,...,bm¬
Kết quả ghi ra file văn bản SUBST.OUT:
 Dòng thứ nhất ghi số k là số lượng số hạng của dãy C
 Dòng thứ hai chứa k số hạng của dãy C
 Dòng thứ ba chứa k chỉ số trong dãy A của k số hạng dãy C
 Dòng thứ tư chứa k chỉ số trong dãy B của k số hạng của C

SUBST.INP
7 8
2 5 8 3 4 6 7
1 4 2 5 3 7 9 10
SUBST.OUT
4
2 5 3 7
1 2 4 7
3 4 5 6

#include <bits/stdc++.h>
#define N 107

using namespace std;

int n, m, res;
int a[N], b[N];
int f[N][N];
stack <int> sta, stb, stc;

int main () {
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
freopen ("SUBST.INP", "r", stdin);
freopen ("SUBST.OUT", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= m; ++i) cin >> b[i];

for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
if (a[i] == b[j]) f[i][j] = f[i-1][j-1] + 1;
else f[i][j] = max (f[i-1][j], f[i][j-1]);

res = f[n][m];
while (f[n][m] != 0) {
if (a[n] == b[m]) {
sta.push(n);
stb.push(m);
stc.push(a[n]);
--n, --m;
} else {
if (f[n][m] == f[n-1][m]) --n;
else --m;
}
}

cout << res << '\n';
while (stc.size()) cout << stc.top() << ' ', stc.pop(); cout << '\n';
while (sta.size()) cout << sta.top() << ' ', sta.pop(); cout << '\n';
while (stb.size()) cout << stb.top() << ' ', stb.pop();
return 0;
}

#include <bits/stdc++.h>
#define ii pair <int, int>
#define iii pair <int, ii>
#define F first
#define S second
#define N 10007

using namespace std;

int n;
int l[N], t[N];
iii a[N];

bool check (int i, int j) {
if (a[i].S.F > a[j].F) return false;
return true;
}

int main () {
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
freopen ("ACTIVITY.INP", "r", stdin);
freopen ("ACTIVITY.OUT", "w", stdout);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i].F >> a[i].S.F, a[i].S.S = i;
sort (a+1, a+n+1);
a[0] = {0, {0, 0}};
a[n+1] = {a[n].S.F+1, {a[n].S.F+2, n+1}};
l[n+1] = 1;

for (int i = n; i >= 0; --i) {
int jmax = n+1;
for (int j = i+1; j <= n+1; ++j)
if (check (i, j) && l[j] > l[jmax]) jmax = j;
l[i] = l[jmax] + 1;
t[i] = jmax;
}

cout << l[0] - 2 << '\n';
int i = t[0];
while (i != n+1) {
cout << a[i].S.S << ' ';
i = t[i];
}
return 0;
}

#include<bits/stdc++.h>
#define N 101
using namespace std;
struct kien{
int x,id;
};
kien a1[N],b1[N]; int d[N][N],a[N],b[N],c[N]; int n,m,p=0,ans=0;
void inp(){
cin>>n>>m;
for(int i=1; i<=n; i++) cin>>a[i];
for(int i=1; i<=m; i++) cin>>b[i];
for(int i=1; i<=n; i++)
if(a[i]!=b[i]){
p++;
a1[p].x=a[i]; a1[p].id=i;
b1[p].x=b[i]; b1[p].id=i;
}
if(n>m){
m=p;
for(int i=m; i<=n; i++){
p++;
a1[p].x=a[i]; a1[p].id=i;
}
n=p;
}
else if(m>n){
n=p;
for(int i=n; i<=m; i++){
p++;
b1[p].x=b[i]; b1[p].id=i;
}
m=p;
}
}
void solve(){
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
if(a1[i].x==b1[j].x) d[i][j]=d[i-1][j-1]+1;
else d[i][j]=max(d[i-1][j],d[i][j-1]);
cout<<d[n][m]<<"\n";
int i=n,j=m;
while(i>0 && j>0)
if(a1[i].x==b1[j].x){
c[++ans]=a1[i].x;
a[ans]=a1[i].id; b[ans]=b1[j].id;
i--; j--;
}else{
if(d[i-1][j]>=d[i][j-1]) i--;
else j--;
}
for(int i=ans; i>=1; i--) cout<<c[i]<<" "; cout<<"\n";
for(int i=ans; i>=1; i--) cout<<a[i]<<" "; cout<<"\n";
for(int i=ans; i>=1; i--) cout<<b[i]<<" ";
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
freopen("subst.inp","r",stdin);
freopen("subst.out","w",stdout);
inp();
solve();
}

#include<bits/stdc++.h>
#define nmax 107

using namespace std;

int n, m;
int a[nmax], b[nmax];

void inp(){
cin >> n >> m;
for(int i = 1; i <= n; i++)
cin >> a[i];
for(int i = 1; i <= m; i++)
cin >> b[i];
}

void get(int a[], int b[]){
int res;
string c = "";
int L[n + 1][m + 1];

for(int i = 0; i <= n; i++)
L[i][0] = 0;
for(int j = 0; j <= m; j++)
L[0][j] = 0;

for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(a[i-1] == b[j-1]){
L[i][j] = L[i-1][j-1] + 1;
}
else{
if(L[i-1][j] >= L[i][j-1])
L[i][j] = L[i-1][j];
else
L[i][j] = L[i][j-1];
}
}
}
res = L[n][m];
int i = n;
int j = m;
while(L[i][j] != 0){
if(a[i-1] == b[j-1]){
c += a[i-1];
i--;
j--;
}
else{
if(L[i-1][j] >= L[i][j-1])
i--;
else
j--;
}
}

cout << res << '\n';
for(int t = res - 1 ; t >= 0; t--)
cout << (int) c[t] << ' ';
cout << '\n';
for(int t = res - 1 ; t >= 0; t--)
for(int i = 1; i <= n; i++)
if(a[i] == (int)c[t]) cout << i << ' ';
cout << '\n';
for(int t = res - 1 ; t >= 0; t--)
for(int i = 1; i <= m; i++)
if(b[i] == (int)c[t]) cout << i << ' ';
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
inp();
get(a,b);
return 0;
}

Code:

#include <iostream>
#include <fstream>
#include <math.h>
using namespace std;
void doctep();
void qhd2();
void ghitep();
long a[10000],b[10000];
long fx[10001][10001];
long m,n;
int main()
{
   doctep();
   ghitep();
   return 0;
}
void qhd()
{
   for (long i=1;i<=n;i++)
       fx[i][0]=0;
   for (long j=1;j<=m;j++)
       fx[0][j]=0;
   for (long i=1;i<=n;i++)
       for (long j=1;j<=m;j++)
       if (a[i]==b[j])
       fx[i][j]=fx[i-1][j-1]+1;
   else fx[i][j]=max(fx[i][j-1],fx[i-1][j]);

}
void doctep()
{
   ifstream fi("dcc.inp");
   fi>>n>>m;
   for (long i=1;i<=n;i++)
       fi>>a[i];
   for (long j=1;j<=m;j++)
       fi>>b[j];
   fi.close();

}
void ghitep()
{
   qhd();
   ofstream fo("dcc.out");
   fo<<fx[n][m];
   fo.close();
}
]

#include <bits/stdc++.h>
#define nmax 100007
#define For(i, a, b) for(int i = a ; i <= b ; i++)

using namespace std;

int a[nmax], b[nmax], n, m;
vector<int> c, vta, vtb;

int main()
{
freopen("SUBST.inp","r",stdin);
freopen("SUBST.out","w",stdout);
cin >> n >> m;
For(i, 1, n) cin >> a[i];
For(i, 1, m) cin >> b[i];
int x = 1;
For(i, 1, n)
For(j, x, m)
if(a[i] == b[j])
{
c.push_back(a[i]);
vta.push_back(i);
vtb.push_back(j);
x = j + 1;
}
cout << c.size() << '\n';
for(int i = 0 ; i < c.size() ; i++) cout << c[i] << " "; cout << '\n';
for(int i = 0 ; i < c.size() ; i++) cout << vta[i] << " "; cout << '\n';
for(int i = 0 ; i < c.size() ; i++) cout << vtb[i] << " ";
return 0;
}