Editorial for AVERAGE

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.

Author: Yunan

Nguồn: Free Contest

Với một dãy số $p_1, p_2, . . . , p_k$ ~p_1, p_2, . . . , p_k~ bất kì, khi trừ mỗi phần tử của dãy $p$ ~p~ đi một lượng là $x$ ~x~ thì trung bình cộng của dãy p cũng sẽ giảm đi $x$ ~x~. Do đó, ta có thể trừ mỗi phần tử của dãy $x$ ~x~ đi một lượng là $a$ ~a~. Khi đó, bài toán trở thành đếm số lượng dãy con của $x$ ~x~ có tổng giá trị các phần tử của dãy con bằng $0$ ~0~.

Ta có thể giải bài toán này bằng quy hoạch động. Gọi $dp[i][j]$ ~dp[i][j]~ là số dãy con của dãy $x_1, x_2, . . . , x_i$ ~x_1, x_2, . . . , x_i~ có tổng bằng $j$ ~j~. Ta có công thức QHĐ như sau:

$\displaystyle dp[i][j] = dp[i - 1][j] + dp[i - 1][j - x_i]$

Trong công thức trên, $dp[i - 1][j]$ ~dp[i - 1][j]~ ứng với trường hợp không chọn phần tử $x_i$ ~x_i~ vào dãy con, $dp[i - 1][j - x_i]$ ~dp[i - 1][j - x_i]~ ứng với trường hợp chọn phần tử $x_i$ ~x_i~ vào dãy con.

Độ phức tạp: $O(n^2.X)$ ~O(n^2.X)~ với $X$ ~X~ là giới hạn giá trị các phần tử $x_i$ ~x_i~ trong đề bài.

Editorial for AVERAGE

Comments