STMERGE - VOI 2013 - Trộn xâu
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Cho 2 xâu ký tự X = x 1 , x 2 , .., x m và Y = y 1 , y 2 , ..., y n . Cần xây dựng xâu T = t 1 , t 2 , t 3 , ..,t n+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 X và Y để thu được xâu T được tính bởi công thức c( T ) = sum(c( t k , t k+1 )) với k = 1, 2, .., n+m-1; trong đó, các chi phí c( t k , t k+1 ) được tính như sau:
- Nếu hai ký tự liên tiếp t k , t k+1 được lấy từ cùng một xâu X hoặc Y thì c( t k , t k+1 ) = 0
- Nếu hai ký tự liên tiếp t k , t k+ 1 là x i y j thì chi phí phải trả là c( x i , y j ). Nếu hai ký tự liên tiếp t k , t k+1 là y j , x i thì chi phí phải trả là c( y j , x i ) = c( x i , y j )
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( x i , y 1 ), c( x i , y 2 ), …, c( x i , y n ), 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
- Người up: voj
- Nguồn bài: VOI 2013 - Ngày 2