150 Bài Toán Tin Đại học Sư Phạm Hà Nội 2004 – 2006 phần 5 pps

74

064. TRỌNG SỐ XÂU

Xét tập chữ cái A = {I, W, N}. Một từ là một dãy liên tiếp không quá 6 ký tự của A.

Cho một danh sách L gồm m từ phân biệt.

• Mỗi từ trong danh sách được gán một trọng số dương ≤ 60000.

• Những từ không có trong danh sách mang trọng số 0.

Xét một xâu S chỉ gồm các ký tự trong A. Trọng số của xâu S được tính bằng tổng trọng số các từ

trong S. (Các từ trong S được liệt kê dưới dạng các đoạn ký tự liên tiếp của S tính cả việc giao nhau

và chứa nhau)

Yêu cầu: Cho trước danh sách L và độ dài n ≤ 100. Hãy tìm xâu S = S1S2...Sn có trọng số nhỏ

nhất. Nếu có nhiều xâu S đều có trọng số nhỏ nhất thì chỉ cần chỉ ra một xâu.

Dữ liệu: Vào từ file văn bản STR.INP

• Dòng 1: Ghi hai số n, m cách nhau một dấu cách.

• m cặp dòng tiếp theo, cặp dòng thứ i gồm 2 dòng:

♦ Dòng thứ nhất ghi từ thứ i trong danh sách L

♦ Dòng thứ hai ghi trọng số của từ đó

Kết quả: Ghi ra file văn bản STR.OUT gồm 2 dòng:

• Dòng 1: Ghi trọng số của từ S tìm được

• Dòng 2: Ghi xâu ký tự S

Ví dụ:

STR.INP STR.OUT STR.INP STR.OUT

8 10

I

13

W

6

N

12

II

6

NI

6

IIN

13

WWW

7

WNN

23

NWW

18

NWN

0

62

WWIWWIWW

8 8

W

10

I

10

N

30

WI

1

WW

10

II

11

WIW

2

IWI

3

98

IWIWIWIW