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

Chúng tôi nhận thiết kế web công ty, thiết kế web thương mại điện tử, shop, thiết kế web blog cá nhân, viết phần mềm PC.

Liên hệ ngay: 035.870.8844 - Giá chỉ từ 2-3 triệ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 *