DAYSO6 - Dãy số (OLP Không chuyên 2009)

Cho dãy số gồm n số nguyên a₁, a₂, …, a_n. Tìm giá trị lớn nhất của hàm f(i, j, k) = a_i + 2×a_j + 3×a_k với 1≤ i < j < k ≤ n.
Ví dụ: với dãy gồm 5 số -1, 2, -2, -3, 5 thì f(1, 2, 5)= -1 + 2×2 + 3×5 = 18 là lớn nhất.

Dữ liệu nhập:

- Dòng thứ nhất là số nguyên n (3 ≤ n ≤ 10⁵).

- Dòng thứ hai là n số nguyên a₁, a₂, …, a_n  mỗi số cách nhau một khoảng trắng (|a_i| ≤ 10⁹)

Dữ liệu xuất:

- Là giá trị lớn nhất của hàm f(i, j, k) tìm được.

Ví dụ

• input
  5
  -1 2 -2 -3 5
  output
  18

Nộp bài

Lần 1:
- Liệt kê ra các đặc điểm:
   +) 3 số có thứ tự trước sau i<j<k
   +) n^5 nên thuật toán O(n^2) ko được
   +) Để f(i,j,k) có giá trị lớn nhất thì a[k] > a[j] > a[i] càng tốt.

=> Bài toán có thể quy về tìm bộ i<j<k sao cho a[i] < a[j] < a[k]. Tức là một dãy tăng dần.
Xuất hiện yếu tố tăng dần => Thử nghĩ xem kỹ thuật sắp xếp có áp dùng gì vào được bài toán này không?

Giả sử nếu áp dụng thuật toán sắp xếp, lúc này ta có một dãy tăng dần.
Lúc này ta cần tìm từ cuối dãy trở về lấy bộ 3 có chỉ số giảm dần là được?

=> Đã thử và sai ngay ở test #3 
Code: https://ideone.com/aCki1o

Xem lại test...

Input

5
5 4 3 2 1

Output

15

Đáp án

22

Như vậy nếu như phần tử đầu tiên là phần tử lớn nhất thì, khi sắp xếp nó sẽ xuống cuối , và khi tìm ngược về sẽ không có phần tử nào có chỉ số nhỏ hơn nó cả, tức là không đủ 3 số!
Như vậy đây là sai sót do kỹ thuật, chưa làm được đúng theo như ban đầu đã yêu cầu!

=> Đổi về tên bài toán như thế này sẽ dễ làm hơn: (Giả sử đã sắp xếp xong) Duyệt từ đầu đến cuối, tìm bộ 3 phần tử phía cuối cùng có chỉ số tăng!
=> Nhưng vẫn có trường hợp không có, do nếu dãy ban đầu là giảm dần, và khi sắp xếp nó lại thành tăng dần, và không thể tìm ra một bộ nào có chỉ số tăng cả!

5 tiếng sau...
Do thời gian có hạn nên đành chuyển sang việc nhìn đáp án để tiết kiệm thời gian, vì thời gian không còn nhiều!

Lần 2: [copied]
Do mục tiêu trong thời gian này làm xem nhiều bài nhất có thể nên, xin phép được sử dụng cách giải quyết của các bạn khác trong phần này!

Ta có 3 hàm f,g,h, trong đó:
f[i] = max(a[1]....a[i]) : Giá trị lớn nhât từ a[1] đến a[i].
g[i] = max(2*a[i] + f[j<i]) : Giái trị lớn nhất trước đó của f() + 2*a[i]. Tức là kết quả của bài toán tìm max cho biêu thức F = a[i] + 2*a[j] với i < j.
h[i] = max(3*[i] + g[j<i]) : Giá trị lớn nhất trước đó của g() + 3*a[i]. Tức là kết quả của bài toán tìm max cho biểu thức F = g() + 3*a[i] = f() + 2*a[j] + 3*a[i] = a[k] + 2*a[j] + 3*a[i].

Như vậy, bài toán giải bằng cách quy về bài toán nhỏ hơn là tìm max cho biểu thức F = a[i] + 2*a[j] với i<j.

=> Công việc chỉ là xây dựng các hàm f,g,h và kết quả chính là h[n].
Code: http://ideone.com/pk36t5

#namlunoy