Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

STMERGE - VOI 2013 - Trộn xâu

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+1 yj, 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

Được gửi lên bởi:VOJ Team
Ngày:2013-01-12
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM32-GCC ASM64 MAWK BC C-CLANG CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY KTLN NIM OBJC OBJC-CLANG OCT PERL6 PICO PROLOG PYPY R RACKET RUST CHICKEN SED SQLITE SWIFT UNLAMBDA VB.NET
Nguồn bài:VOI 2013 - Ngày 2

hide comments
2018-08-06 04:43:17
nhat hao sach
2018-06-23 17:44:23
nhầm m với n mất tiêu một đấm AC =((
2017-11-05 15:58:05
nhật hào sạch
2017-08-21 10:37:09 Ðặng Minh Tiến
https://kienthuc24h.com/stmerge-spoj-voi-2013-tron-xau/
2017-08-06 11:01:10
xem con thức QHĐ ở https://vietcodes.github.io/code/29
2017-05-15 02:19:08
Mạnh béo vl
2017-05-14 17:54:04
Nah
2015-08-26 13:55:12 White Shadow
one hit =))
2014-12-25 14:21:34 [ND] HI
y1y2x1x2y3 = 6
2014-12-01 13:57:14 Tây Cuồng
Lâu rồi mới 1 đấm AC :D :))
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.