Editorial for Bedao Regular Contest 13 - EVAL
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Nhận xét: giá trị kì vọng của hàm call(a, b)
và call(c, d)
sẽ bằng nhau nếu ~b - a = d - c~.
Gọi ~f[i]~ là giá trị kì vọng của hàm call(l, r)
với ~r - l + 1 = i~. Ta có công thức quy hoạch động sau:
~f[i] = (1 + f[i]) + \sum \limits_{j = 1}^{i - 2} (1 + f[j] + f[i - j - 1]) + (1 + f[i])~
~\Rightarrow f[i] = i + 2 \cdot f[i] + \sum \limits_{j = 1}^{i - 2} (f[j] + f[i - j - 1])~
~\Rightarrow (i - 2) \cdot f[i] = i + \sum \limits_{j = 1}^{i - 2} (f[j] + f[i - j - 1])~
~\Rightarrow f[i] = \dfrac{i + \sum \limits_{j = 1}^{i - 2} (f[j] + f[i - j - 1])}{i - 2}~
Để tính nhanh ~\sum \limits_{j = 1}^{i - 2} (f[j] + f[i - j - 1])~, ta có thể sử dụng prefix sum (tổng tiền tố).
Độ phức tạp: ~O(n)~.
Comments