DAYSO2 - Dãy số 2 (OLPCĐ 2014)

Cho dãy số gồm n số nguyên a₁, a₂, ..., a_n. Một đoạn con của dãy đã cho là dãy a_i,..., a_j (1 ≤ i ≤ j ≤ n), dãy có độ dài (j - i + 1) và có trọng số bằng tổng (a_i + ... + a_j).

Yêu cầu: Tìm đoạn con có độ dài là một số chia hết cho 3 và có trọng số lớn nhất.

Dữ liệu nhập:

- Dòng đầu ghi số nguyên n (3 ≤ n ≤ 100.000).

- Dòng thứ hai ghi n số nguyên a₁, a₂, ..., a_n (|a_i| < 10⁹).

Dữ liệu xuất:

- Giá trị trọng số của đoạn con tìm dược.

Ví dụ

• input
  11
  1 1 1 -9 1 1 1 1 -1 1 -9
  output
  4
• input
  3
  1 2 3
  output
  6
• input
  4
  -1 5 -10 1
  output
  -4

Nộp bài

Lần 1:

Hoạt đầu nhìn có vẻ dễ, và cách đầu tiên nghĩ đến là đặt T[i] là tổng từ a[0] tới a[i], tổng từ a[i] đến a[j] chính là T[j] - T[i-1].
Nhưng cách này độ phức tạp vẫn là O(n^2) vì phải duyệt i và j để tính theo cặp!
Mặt khác n = 10^5 => Độ phức tạp ko để n^2 được.

Thực nghiệm chạy theo cách này sẽ bị TLE tại test 27!
Code: http://ideone.com/a85pBF

Lần 2: [copied]
Sau khi đi đọc bài giải của các bạn khác thì đã biết được cách làm! 
Như vậy là trong bài này cần thêm một mẹo nhỏ!
Nhớ lại cách trên thì việc mất thời gian nhất là duyệt 2 vòng for để tìm ra cặp (i,j) phù hợp!

Dựa vào yêu cầu đề bài là dãy này là dãy con liên tiếp và có số phần tử chia hết cho 3 ta có một số nhận xét như sau:
==> Dãy con này có số lượng phần tử chia hết cho 3 => Nó là tổng của các dãy con liên tiếp có 3 phần tử. Ví dụ: [1,6] = [1,3] + [4,6]

Từ nhận xét trên ta đi đến phương án QHĐ mới như sau:
Gọi t3[i] là tổng của 3 phần tử liên tiếp t3[i] = a[i] + a[i-1] + a[i-2].
Gọi T[i] là tổng lớn nhất của dãy con liên tiếp có số phần tử chia hết cho 3.
Như vậy kết quả cần tìm là max(T[i]).

(Note: ở đây ta đánh số từ 1 cho nó thuận miệng!)*Cơ sở QHĐ
- Dãy t3 đã được tính.
- T[1] = 0, T[2] = 0 (Do số lượng phần tử của nó chưa đủ), T[3] = t3[3] = a[1] + a[2] + a[3].

* Thử tiếp để ra công thức:
Vậy với T[4] = t3[4] (tổng liên tiếp 4-3-2) + T[4-3 = 1] (T[1] : tổng lớn nhất của bộ tìm được trước đó) 

*Công thức truy hồi: T[i] = max(t3[i], t3[i] + T[i-3])

Code [AC] : http://ideone.com/qe9igU

Bài học:
Bài học lần này là, kết quả quy hoạch động ko nhất thiết phải dựa vòa thằng trước nó, mà có thể dựa vào kết quả trước đó vài bước, và 1 phần tử có thể biểu diễn kết quả của một số phần tử trước đó chứ không phải tất cả!

Cần tập trung phân tích vào những dữ kiện đặc biệt của bài toán!

#namlunoy