COPYDNA

[Trung]

Cho một xâu DNA S gồm các ký tự {A, C, G, T}. Bạn sẽ làm việc trên một
xâu T, ban đầu có giá trị rỗng. Tìm số thao tác sao chép nhỏ nhất để
biến T thành một xâu cho trước. Biết rằng mỗi thao tác sao chép có một
trong hai dạng:
• sao chép S i j k: sao chép đoạn S[i..j] vào xâu T bắt đầu từ vị trí
k
• sao chép T i j k: sao chép đoạn T[i..j] vào xâu T bắt đầu từ vị trí
k
Lưu ý nếu i > j có nghĩa là ta sao chép đoạn xâu theo thứ tự ngược.
Mỗi ký tự trong T chỉ được tạo ra đúng một lần, nghĩa là không được
sao chép đè lên ký tự đó.
Ví dụ: Với S = “ACTG” hãy tạo T = “GTACTATTATA”
1. Tạo GT......... bằng cách sao chép và đảo xâu “TG” từ S.
2. Tạo GTAC....... bằng cách sao chép “AC” từ S.
3. Tạo GTAC...TA.. bằng cách sao chép “TA” từ T.
4. Tạo GTAC...TAAT bằng cách sao chép và đảo xâu “TA” từ T.
5. Tạo GTACAATTAAT bằng cách sao chép “AAT” từ T.

Với mỗi test, in ra số thao tác sao chép ít nhất để tạo ra T từ S,
hoặc in ra "impossible" nếu không thể làm

Solution:
Sol:
Quy hoạch động trạng thái:
Gọi f[mask] = chi phí nhỏ nhất để xây dựng nốt T nếu đã xây dựng các
ký tự ở các vị trí thuộc tập mask.
Nhận xét: nếu có thể thêm một đoạn (i,j) vào xâu đang xây dựng, thì
cách thêm xâu (i,j) luôn không tồi hơn cách thêm xâu (i’, j’) với (i ≤
i’ và j’ ≤ j).
Chú ý rằng, số lượng trạng thái rất lớn, nhưng trên thực tế lại khá
nhỏ (vì ta bỏ qua các trường hợp thêm xâu (i’, j’). Do vậy, ta sử dụng
phương pháp quy hoạch động đệ quy. Với mỗi trạng thái của mask, ta xét
tất cả các trạng thái mask’ có thể đến được từ mask bằng cách thêm
những đoạn xâu dài nhất có thể.