Editorial for Bedao Grand Contest 12 - FENCE


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: bedao

Dựa vào điều kiện ~2\cdot h_i > n~, có thể nhận giá trị bất kì, ta chia dãy độ dài ~m~ ra thành các phần, mỗi phần bắt đầu là một giá trị bất kì và kết thúc khi thỏa mãn điều kiện thứ 2.

Dựa vào điều kiện thứ 3, ta nhận thấy mỗi phần có độ dài tối đa là ~log_2(n)~.

Định nghĩa ~f[i][len]~ là số phần bắt đầu bằng thanh gỗ độ dài ~i~, và phần này có độ dài ~len~: ~f[i][len] = \sum_{j=i\times 2}^n f[j][len-1]~.

Ta có thể tính nhanh ~f[i][len]~ trong ~O(1)~ bằng tổng tiền tố.

Gọi ~cnt[len]~ là số phần có độ dài len, ta có: ~cnt[len] = \sum^n_{i=1} f[i][len]~.

Gọi ~dp[i]~ là số hàng rào đẹp độ dài ~i~, ta có: ~dp[i] = \sum^{min(log_2(n),i)}_{j=1} cnt[j]\times dp[i-j]~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.