LNACS spoj – Dãy con chung không liền kề dài nhất

Nguồn đề bài: http://vn.spoj.com/problems/LNACS/

1. Đề bài LNACS spoj

Dãy C = c1, c2, …, ck là dãy con không liền kề của dãy A = a1, a2, …, am nếu C có thể nhận được bằng cách chọn một dãy các phần tử không liền kề của A, nghĩa là tìm dược dãy các chỉ số i1, i2, …, ik sao cho:

1 ≤ i1, i2, …, ik ≤ m;
i1 < i2 – 1, i2 < i3 – 1, …, ik – 1 < ik – 1;
c1 = ai1, c2 = ai2, ck = aik.

Ta gọi độ dài của dãy số là số phần tử của nó.

Cho hai dãy:
A = a1, a2, …, am

B = b1, b2, …, bn

Dãy C được gọi là dãy con chung không liền kề của hai dãy A và B nếu như nó vừa là dãy con không liền kề của A, vừa là dãy con không liền kề của B.

Yêu cầu

Cho hai dãy số A và B. Hãy tìm độ dài của dãy con chung không liền kề dài nhất của hai dãy đã cho.

Dữ liệu

  • Dòng đầu tiên chứa hai số nguyên dương m và n (2 ≤ m, n ≤ 103) được ghi cách nhau bởi dấu cách, lần lượt là số lượng phần tử của dãy A và dãy B.
  • Dòng thứ i trong m dòng tiếp theo chứa số nguyên không âm ai (ai ≤ 104), i = 1, 2, …, m.
  • Dòng thứ j trong n dòng tiếp theo chứa số nguyên không âm bj (bj ≤ 104), j = 1, 2, …, n.

Kết quả

Ghi ra trên một dòng duy nhất độ dài của dãy con chung không liền kề dài nhất của hai dãy A và B.

Ví dụ

Input:
4 5
4
9
2
4
1
9
7
3
4

Output:
2

2. Gợi ý LNACS spoj

Bài này làm quy hoạch động tương tự bài dãy con chung dài nhất. Tuy nhiên có một chút khác ở công thức.

Gọi f[i][j] là độ dài dãy con chung dài nhất của 2 dãy a[1…i] và b[1…j]. Ta có:

  • nếu a[i]!=b[j] thì: f[i][j]=max(f[i-1][j], f[i][j-1],f[i-1][j-1]).
  • nếu a[i]==b[j] thì: f[i][j]=max(f[i-1][j], f[i][j-1],f[i-1][j-1],f[i-2][j-2]+1).

Về phần khởi tạo:

f[0][0] =0;

f[1][j]   = 1 nếu a[1]==b[j].

= f[1][j-1] nếu a[1]!=b[j].

f[i][1]   = 1 nếu a[i]==b[1].

= f[i-1][1] nếu a[i]!=b[1].

3. Code mẫu LNACS spoj

#include <bits/stdc++.h>

using namespace std;
    int m,n,a[1001],b[1001],f[1001][1001];
int main()
{
    cin>>m>>n;
    for(int i=1; i<=m; i++)
        cin>>a[i];
    for(int j=1; j<=n; j++)
        cin>>b[j];
    f[0][0]=0;
    for(int i=1; i<=m; i++)
        f[i][1]=(a[i]==b[1])?1:f[i-1][1];
    for(int j=1; j<=n; j++)
        f[1][j]=(a[1]==b[j])?1:f[1][j-1];
    for(int i=2; i<=m; i++)
        for(int j=2; j<=n; j++)
    {
        f[i][j]=max(f[i][j-1],max(f[i-1][j],f[i-1][j-1]));
        if(a[i]==b[j])f[i][j]=max(f[i][j],f[i-2][j-2]+1);
    }
    cout<<f[m][n];
}

One thought on “LNACS spoj – Dãy con chung không liền kề dài nhất

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *