Thư viện tri thức trực tuyến
Kho tài liệu với 50,000+ tài liệu học thuật
© 2023 Siêu thị PDF - Kho tài liệu học thuật hàng đầu Việt Nam
Tài liệu đang bị lỗi
File tài liệu này hiện đang bị hỏng, chúng tôi đang cố gắng khắc phục.
150 Bài Toán Tin Đại học Sư Phạm Hà Nội 2004 – 2006 phần 5 pps
Nội dung xem thử
Mô tả chi tiết
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