Các nhà sinh học phát hiện ra một loại chuỗi DNA lạ. Nó được mô tả như một chuỗi gồm 𝒏 ký tự xây dựng từ tập {𝑨,𝑩}. Một chuỗi DNA không thể đột biến được nữa nếu chuỗi đó chỉ gồm toàn ký tự A. Ví dụ chuỗi 𝑨𝑨𝑨 là một chuỗi không thể đột biến nữa. Các nhà sinh học phát hiện ra điều kỳ lạ này và đã tiến hành nghiên cứu chi tiết hơn. Họ phát hiện ra chỉ có hai loại đột biến cho loại DNA này. Loại đột biến thứ nhất là hoán đổi một ký tự bất kỳ của chuỗi theo quy tắc 𝑨 → 𝑩 hoặc B → A. Loại đột biến thứ hai thay đổi tiền tố của chuỗi. Cụ thể là thay đổi tất cả các ký tự từ vị trí 1 đến vị trí 𝒌 (𝟏 ≤ 𝒌 ≤ 𝒏) với quy tắc 𝑨 → 𝑩 hoặc B → A.
Yêu cầu: Hãy tính số phép đột biến ít nhất để biến đổi một chuỗi DNA ban đầu sang chuỗi DNA kết thúc chỉ chứa toàn ký tự 𝑨. Đây là loại chuỗi DNA không thể đột biến được nữa.
Dữ liệu: Vào từ file văn bản DNA.INP: - Dòng đầu tiên chứa số nguyên 𝒏 với 1 ≤ 𝑛 ≤ 106; - Dòng thứ hai chứa xâu ký tự 𝒔 chỉ trạng thái đầu tiên của chuỗi DNA.
Kết quả: Đưa ra file văn bản DNA.OUT gồm 1 dòng duy nhất ghi số lần biến đổi ít nhất để đưa chuỗi DNA từ trạng thái 𝒔 về trạng thái không đột biến được nữa.
Ví dụ:
| DNA.INP | DNA.OUT |
|
4 ABBA |
2 |
|
12 AAABBBAAABBB |
4 |
mk xin chia sẻ code nhé:
#include<cstdio> inline int min( int a, int b ) { return a>b?b:a; } char s[1000005]; int f[1000005], g[1000005]; int main() { int n; scanf("%d", &n); scanf("%s", s); f[0] = g[0] = 0; for(int i=0; i<n; i++) if( s[i] == 'A' ) { f[i+1] = f[i]; g[i+1] = 1 + min( f[i], g[i] ); } else { g[i+1] = g[i]; f[i+1] = 1 + min( f[i], g[i] ); } printf("%d\n", f[n]); }
