giúp tớ đề thi lớp 10.

[bumzunpilo]

Ta gọi một dãy chia hết hoàn toàn là dãy a1, a2, …, aN với aj chia hết cho a¬i với i<j. Một dãy con của một dãy là một dãy được thiết lập bằng cách xoá một số phần tử nào đó trong dãy.
Ví dụ: 3, 7, 11, 3 là một dãy con của dãy 6, 3, 11, 5, 7, 4, 3, 11, 5, 3 nhưng 3, 3, 7 không phải là một dãy con của dãy 6, 3, 11, 5, 7, 4, 3, 11, 5, 3 và 3, 15, 60, 720 là một dãy chia hết.
Yêu cầu: Cho một dãy các số nguyên, tìm dãy con chia hết hoàn toàn có độ dài lớn nhất trong dãy đã cho.
Dữ liệu vào: Cho trong file SEQ.INP có cấu trúc:
• Dòng đầu chứa N là độ dài của dãy.
• Dòng thứ hai chứa N số nguyên ai, mỗi số cách nhau một dấu cách.
Dữ liệu ra: Kết quả ghi vào file SEQ.OUT:
• Chứa độ dài lớn nhất của dãy con chia hết hoàn toàn tìm được.
Giới hạn: N <= 10000.
-50000<=ai<=50000.


Ai giải giúp với, nếu là quy hoạch động thì chỉ tớ luôn tại sao có công thức truy hồi đó luôn nhá.

[chienphuninh]

Đọc đề chẳng hiểu gì cả. dãy "3, 15, 60, 720 là một dãy chia hết." có liên quan gì đến Input của bài không đấy nhỉ. nó chia hết hoàn toàn cho dãy nào?

[linhhahaduc]

Gọi a là dãy số ban đầu
F[i] : Độ dài dãy con chia hết dài nhất khi kết thúc tại vị trí thứ i
F[i] :=max (F[j] + 1) với j:=1->i-1 và a[i] mod a[j] = 0

[bumzunpilo]

Đọc đề chẳng hiểu gì cả. dãy "3, 15, 60, 720 là một dãy chia hết." có liên quan gì đến Input của bài không đấy nhỉ. nó chia hết hoàn toàn cho dãy nào?

Nó không liên quan tới inp, nhưng nó là ví dụ mà bạn. Nó chia hết hoàn toàn tức là số đứng sau thì luôn chia hết cho mọi số đứng trước.