STMERGE spoj – VOI 2013 – Trộn xâu

Nguồn đề bài: http://vn.spoj.com/problems/STMERGE/

1. Đề bài STMERGE spoj

Cho 2 xâu ký tự X = x1, x2, .., xmY = y1, y2, …, yn. Cần xây dựng xâu T = t1, t2, t3, ..,tn+m. gồm tất cả các ký tự trong xâu X và tất cả các ký tự trong xâu Y, sao cho các ký tự trong X xuất hiện trong T theo thứ tự xuất hiện trong X và các ký tự trong Y xuất hiện trong T theo đúng thứ tự xuất hiện trong Y, đồng thời với tổng chi phí trộn là nhỏ nhất. Tổng chi phí trộn hai xâu XY để thu được xâu T được tính bởi công thức c(T) = sum(c(tk, tk+1 )) với k = 1, 2, ..,  n+m-1; trong đó, các chi phí c(tk, tk+1) được tính như sau:

  • Nếu hai ký tự liên tiếp tk, tk+1 được lấy từ cùng một xâu X hoặc Y thì c(tk, tk+1) = 0
  • Nếu hai ký tự liên tiếp tk, tk+1 là xi yj thì chi phí phải trả là c(xi, yj). Nếu hai ký tự liên tiếp tk, tk+1yj, xi thì chi phí phải trả là c(yj, xi) = c(xi, yj)

Input

Dòng đầu tiên chứa Q là số lượng bộ dữ liệu. tiếp đến là Q nhóm dòng, mỗi nhóm cho thong tin về 1 bộ dữ liệu theo khuôn dạng sau:

  • Dòng thứ nhất chứa 2 số nguyên duong m, n (m, n <= 1000);
  • Dòng thứ i trong m dòng tiếp theo chứa n số nguyên dương, mỗi số không vượt quá 10^9: c(xi, y1), c(xi, y2), …, c(xi, yn), i = 1, 2,…, m.

Ràng buộc : Có 60% số test ứng với 60% số điểm của bài đó có m, n <= 10

Output

  • Gồm Q dòng, mỗi dòng chứa một số nguyên là tổng chi phí theo cách xây dựng xâu T tìm được tương ứng với bộ dữ liệu vào.

Example

Input:

1

2 3

3 2 30

15 5 4

output:

6

2. Hướng dẫn STMERGE spoj

Thuật toán quy hoạch động:

Gọi F[i][j][k] là tổng nhỏ nhất tạo thành từ xâu X[1..i] và Y[1..j], trong đó với k = 0 tương ứng trường hợp kí tự cuối là Y[j] và k = 1 tương ứng kí tự cuối là X[i]

* Trường hợp kí tự cuối là Y[j], tức F[i][j][0], thì kí tự trước đó có hai trường hợp:

–  Y[j-1] Y[j] :

F[i][j][0] = F[i][j-1][0]

–  X[i] Y[j] :

f[i][j][0] = f[i][j-1][1] + c[i][j]

* Trường hợp kí tự cuối là X[i], tức F[i][j][1], thì kí tự trước đó có hai trường hợp

– X[i-1] X[i] :

f[i][j][1] = f[i-1][j][1]

– Y[j] X[i] :

f[i][j][1] = f[i-1][j][0] + c[i][j]

3. Code mẫu STMERGE spoj Pascal và c++

a. code c++

b. Code pascal

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *