DP part 5 - Last version

II.5 Kho báu kia kìa

Bài toán: Cho bản đồ n*m (n, m <=1000). Ô i,j có giá trị là a(i,j)
Ta sẽ xuất phát từ 1 ô bất kì ở cột 1 đến 1 ô bất kì ở cột n . Chi phí đường đi sẽ là tổng giá trị các ô. Ta cần tính đường đi với chi phí nhỏ nhất.
Từ (i,j) --> (i+1,j) hoặc (i,j+1)

VD: Với hình 3*3

1 2 3

4 5 6

7 8 9

DP_part 4

II.4. Bài toán biến đổi xâu

Bài toán: Cho 2 xâu A, B. Ta muốn biến xâu A --> B sau 1 số thao tác và mất một vài chi phí như sau

( lưu ý các phép biến đổi đều chỉ diễn ra trên xâu A) 

+ insert(i,c) -- Chèn vào sau vị trí i , chữ cái c. với chi phí x 

+ replace(i,c) -- thay thế chữ cái thứ i bằng chữ cái c với chi phí y

+ delete(i) xóa chữ cái thứ i với chi phí z

--> in ra chi phí nhỏ nhất.

input:  Nhâp x, y, z và 2 xầu A, B( lenA , lenB <= 1000)

output:  In ra chi phí nhỏ nhất (output đảm bảo <= 10^9)

DP_ part 3

II.3.LCS dãy con chung dài nhất

Ta xét bài toán sau:
Cho 2 xâu, tìm xâu con chung dài nhất của chúng.  độ dài của mỗi xâu <= 1000

Bài toán truy vấn 1:IT

IT:
Cơ bản:
+  QMAX
+  QMAX2
+  NKBRACKE
Trung bình,khó
+ http://vn.spoj.com/problems/PATULJCI/
+ http://vn.spoj.com/problems/GSS/
+ http://tjsct.wikidot.com/usaco-feb08-gold
+ http://usaco.org/index.php?page=viewproblem2&cpid=365