01/10/2018, 16:48

Xin ý tưởng thuật toán

Các nhà sinh học vừa phát hiện ra một loại cấu trúc DNA alpha đặc biệt được cấu trúc bởi chỉ các Nucleotit A và B. Đặc biệt hơn, họ còn phát hiện ra một loại gen omega chỉ gồm nucleotit A nhưng vô cùng hiếm, để nghiên cứu sâu hơn về omega họ quyết định tổng hợp omega từ alpha bằng các phương pháp đột biến nhân tạo. May mắn thay họ tìm ra hai phương pháp đột biến có thể gây ảnh hưởng đến alpha: họ có thể làm thay đổi 1 nuleotit ở một vị trí bất kỳ trên đoạn gen alpha (A thành B hoặc B thành A), phương pháp thứ hai là thay đổi cả đoàn đầu của gen (những nuc A chuyển thành B và ngược lại). Để tiết kiệm chi phí họ quyết định tìm ra số lần gây đột biến ít nhất có thể để biến alpha thành omega.

Hãy giúp họ.

Input
Dòng đầu tiên chứa số tự nhiên n là số nucleotit của gen alpha (1 <= n <= 1000000)

Dòng thứ hai là biểu diễn của gen alpha.

Output
Kết quả bài toán.

Example
Input:
12

AAABBBAAABBB

Output:
4

Plzzz. Mình hơi khó hiểu :v

Huy Le viết 18:49 ngày 01/10/2018

Keyword của thuật toán này là Minimum Edit Distance.

Đỗ Nam viết 18:54 ngày 01/10/2018

<3 Cảm ơn đồng chí :v

Bài liên quan
0