MBLAST - BLAST - Solution for SPOJ

Problem

https://vn.spoj.com/problems/MBLAST

https://oj.vnoi.info/problem/MBLAST

Cho hai xâu A, B. Mở rộng của 1 xâu X là xâu thu được bằng cách chèn (0,1,2 ..) kí tự trống vào xâu. Ví dụ : X là ‘abcbcd’, thì ‘abcb-cd’, ‘-a-bcbcd-‘ và ‘abcb-cd-‘ là các mở rộng của X. (Dấu cách kí hiệu bằng ‘-‘).

A1,B1 là mở rộng của A và B, và giả sử chúng cùng độ dài. Khoảng cách giữa A1 và B1 là tổng khoảng cách giữa các kí tự cùng vị trí. Nếu hai kí tự không là dấu cách thì khoảng cách giữa 2 kí tự này là trị tuyệt đối mã ASCII của chúng. Còn ngược lại, khoảng cách là 1 số K cố định.

Cho hai xâu A, B. Tìm khoảng cách nhỏ nhất giữa hai xâu mở rộng của nó.

Input

Dòng 1 chứa A, dòng 2 chứa B, chỉ gồm chữ thường a-z và số kí tự <=2000.

Dòng thứ 3 là số K, khoảng cách của 1 kí tự bất kỳ với kí tự trống, 1 ≤ K ≤ 100.

Output

Khoảng cách nhỏ nhất.

Sample

blast.in 
cmc 
snmn 
2 
 
blast.out 
10 

blast.in 
koiv 
ua 
1 
 
blast.out 
5

blast.in 
mj 
jao 
4 
 
blast.out 
12 

Tutorial

Gọi F[i][j] là khoảng cách nhỏ nhất đến vị trí i của a và j của b. Khi đó hai kí tự i,j có các cách chọn :

i đi với j : tức là F[i-1][j-1] + a[i]-b[j]
i đi với – và j đi với - : F[i-1][j-1] + 2k
i đi với - : F[i-1][j] + k
j đi với - : F[i][j-1] + k

Do đó F[i][j] là min của 4 giá trị trên.

Cơ sở của bài toán là F[0][i] với F[i][0], nhưng nếu tính ra thì phải xét các trường hợp nên tốt nhất ta tạo hai biến giả trước xâu (‘#’ chẳng hạn), khi đó khoảng cách nhỏ nhất sẽ không đổi (do ‘#’-‘#’ = 0) và F[i][0] = F[0][i] = i*k (dễ thấy điều này)

Submission

MBLAST.cpp

Tutorial SPOJ

MBLAST - BLAST