//
you're reading...
Bài tập huấn luyện

Bài tập huấn luyện: Dãy số

Cho dãy số A gồm N số nguyên. Một dãy con của dãy A là dãy gồm các phần tử A[i1], A[i2], …, A[iM] thỏa mãn 1 ≤ i1 < i2 < … < iM ≤ N. Hãy tìm dãy con B dài nhất thỏa mãn điều kiện:

B[i] = B[i – 1] + B[i – 2] (với i ≥ 3)

InputSEQ.INP

  • Dòng thứ ghi số T là số test.
  • Tiếp theo là 2 × T dòng mô tả T test. Mỗi test được ghi trên 2 dòng:
  • Dòng thứ nhất ghi số N.
  • Dòng thứ hai ghi N số A[1], A[2], …, A[N].

Output:            SEQ.OUT

  • Gồm T dòng, mỗi dòng ghi một số là độ dài dãy con dài nhất thỏa mãn của mỗi test.

Giới hạn:

  • 1 ≤ T ≤ 15.
  • 3 ≤ N ≤ 2500.
  • Các số có trị tuyệt đối không quá 1000000.
  • Thời gian: 2 s/test
  • Bộ nhớ: 25 MB

Ví dụ:

SEQ.INP SEQ.OUT
1

7

-20 87 20 0 20 100 22

4

(Dãy con dài nhất thỏa mãn là -20 20 0 20)

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Tháng Mười 2016
M T W T F S S
« Sep   Nov »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

Fast-flying Falcon

sunset and fishing nets

Force of Life - Pushing Boundaries I

More Photos

Thống kê

  • 81,544 lượt xem

%d bloggers like this: