Nhảy lò cò là trò chơi dân gian của Việt Nam. Người trên hành tinh
X cũng rất thích trò chơi này và họ đã cải biên trò chơi này như sau: Trên mặt
phẳng vẽ n vòng tròn được đánh số từ 1 đến n. Tại vòng tròn i người ta điền số
nguyên dương ai. Hai số trên hai vòng tròn tùy ý không nhất thiết
phải khác nhau. Tiếp đến người ta vẽ các mũi tên, mỗi mũi tên hướng từ một vòng
tròn đến một vòng tròn khác. Quy tắc vẽ mũi tên là: Nếu có ba số ai,
aj, ak thỏa
mãn ak = ai + aj thì vẽ mũi tên hướng từ vòng tròn i
đến vòng tròn k và mũi tên hướng từ vòng tròn j đến vòng tròn k. Người chơi chỉ
được di chuyển từ một vòng tròn đến một vòng tròn khác nếu có mũi tên xuất phát
từ một trong số các vòng tròn, di chyển theo cách mũi tên đã vẽ để đi đến các
vòng tròn khác. Người thắng cuộc sẽ là người tìm được cách di chuyển qua nhiều
vòng tròn nhất.
Ví dụ: Với 5 vòng tròn và các số trong vòng tròn là 1, 2, 8, 3, 5,
trò chơi được trình bày trong hình dưới đây:
Khi đó có thể di chuyển được
nhiều nhất qua 4 vòng tròn (tương ứng với đường di chuyển được tô đậm trên hình
vẽ).
Yêu cầu
Hãy
xác định xem trong trò chơi mô tả ở trên, nhiều nhất có thể di chuyển được qua
bao nhiêu vòng tròn.
Dữ liệu
- Dòng đầu chứa số nguyên n (3 ≤ n ≤ 1000);
- Dòng thứ hai chứa dãy số nguyên dương a1,
a2, ..., an (ai ≤ 109,
i=1, 2,..., n).
Hai
số liên tiếp trên một dòng được ghi cách nhau bởi dấu cách.
Kết quả
Ghi
ra số lượng vòng tròn trên đường di chuyển tìm được.
Ràng buộc
- 60% số tests ứng với 60% số điểm của bài có 3 ≤ n ≤ 100.
Ví dụ:
Dữ liệu:
5
1 2 8 3 5
Kết qủa
4========
Thuật giải:
Tui có tham khảo thuật giải trên các blog, thì thấy là làm Quy hoạch động rồi Tìm kiếm nhị phân......ok!
Thuật giải của tui như sao:
- Sort mảng A tăng trước, tính gì tính
- Xong rồi tui đi xây dựng mảng B, định nghĩa nhé: B[i,j]=true khi có đường nối từ i=>j
cứ theo cái quy tắc của đề bài mà làm tới, gì mà a[i]+a[j]=a[k] thì b[i,k]=true và b[j,k]=true;
- quy hoạch động là đây: tới đây thì dễ rồi, xây dựng mảng C (một chiều): là số điểm đi qua..........
======
Xong rồi, chúc các bạn AC bài này, bài này hay quá
