Dãy số

View as PDF

Submit solution

Points: 0.10 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho dãy ~A~ gồm ~N~ số nguyên. Một dãy con của ~A~ là 1 dãy gồm các phần tử: ~A[i_1]~, ~A[i_2]~, ~\dots~, ~A[i_M]~ thỏa mãn: ~1 \le i_1 < i_2 < \dots < i_M \le N~. Tìm dãy con B của A dài nhất thỏa mãn điều kiện:

~B[i] = B[i-1] + B[i-2]~ với mọi i >= 3.

Input

  1. Dòng 1: ~T~ - số test ~(1 \le T \le 15)~.
  2. Tiếp theo là ~2 \times T~ dòng mô tả các test, mỗi test gồm:
    • Dòng 1: ~N \, (3 \le N \le 2500)~
    • Dòng 2: ~N~ số ~A[1], A[2], ..., A[N]~. Các số có giá trị tuyệt đối không quá ~10^6~.

Output

Gồm ~T~ dòng, mỗi dòng ghi 1 sô nguyên là độ dài dãy con dài nhất.

Sample Input

1
7
-20 87 20 0 20 100 22

Sample Output

4

Comments

Please read the guidelines before commenting.



  • 18
    YugiHackerKhongCopCode   commented on Dec. 31, 2021, 10:46 p.m.

    Cmt này spoil thuật!

    Quy hoạch động

    Gọi ~f[i][j]~ là dãy con dài nhất thỏa mãn đề bài và kết thúc tại ~2~ số ~a_i~ và ~a_j~ (~i < j~)

    ~\Rightarrow~ ~f[i][j] = f[k][i] + 1~ với ~val = a_k = a_j - a_i~ và ~k < i~

    ~\Rightarrow~ ~k~ là vị trí gần ~i~ nhất sao cho ~a_k = val~ (Các bạn tự chứng minh chỗ này nha)

    Note:

    Khởi tạo ~f[i][j] = 2~ ~\forall i < j~

    Lưu được vị trí các số được bằng mảng vì ~|a_i| \le 10^6~

    Duyệt ~j > i~ để tránh trường hợp số ~k~ nằm giữa ~i~ và ~j~

    Độ phức tạp:

    ~O(T.N^2)~