Đây là bài F ACM ICPC Regional Việt Nam 2017. Đầu tiên, gọi $f_{i,j}$ là tổng chi phí nhỏ nhất khi chia $j$ phần tử đầu tiên thành $i$ đoạn, có ngay công thức truy hồi là:
$f_{i,j}=\min_{k=1}^{j} f_{i-1,k-1}+C(k,j)$. Đáp án chính là $f_{d,n}$.
Tuy nhiên độ phức tạp nếu tính trâu quy hoạch động là $O(dn^2)$ quá chậm, vì thế ta thử tối ưu bằng chia để trị (DP DNC).
Trước tiên, xét hàm $C(l,r)$, có 2 trường hợp:
- Trường hợp 1: $K=1$ ta có $C(l,r)=min_{z \in \mathbb{Z}} \sum_{i=l}^{r} |a_i-z|$, là một tổng quen thuộc và đạt giá trị cực tiểu khi $z$ là trung vị của dãy đó. Đặt $mid=l+\lfloor{\frac{r-l+1}{2}}\rfloor$ được $z=a_{mid}$ (do dãy $a$ không giảm).
Tiếp tục biến đổi, với $K=1$ ta có:
$C(l,r)=\sum_{i=l}^{r}|a_i-a_{mid}|=a_{mid}\cdot(mid-l)-(\sum_{i=l}^{mid-1}a_i)-a_{mid}\cdot(r-mid)+(\sum_{i=mid+1}^{r}a_i)$
$=a_{mid}(2\cdot mid-l-r)-S(l,mid-1)+S(mid+1,r)$ với $S(l,r)$ là tổng các phần tử $a_i$ với $(l\leq i\leq r)$.
Từ đây tính được $C(i,j)$ với $1\leq i\leq j\leq n$ trong $O(n^2)$.
- Trường hợp 2: $K=2$ ta có $C(l,r)=min_{z \in \mathbb{Z}} \sum_{i=l}^{r} (a_i-z)^2=z^2(r-l+1)-2zS(l,r)+S'(l,r)$ với $S'(l,r)=\sum_{i=l}^{r}a_i^2$.
Thấy ngay rằng đây là một hàm bậc 2 có biến là $z$ và $r-l+1>0$ nên đạt cực tiểu tại $z=\frac{S(l,r)}{r-l+1}$, vì giá trị này có thể không nguyên nên ta thử 2 giá trị nguyên gần nhất.
Trường hợp $K=2$ ta cũng tính được $C(l,r)$ trong $O(n^2)$. Tiếp theo ta đi chứng minh ta có thể sử dụng chia để trị để giải quyết bài toán. Gọi $opt(i,j)$ là giá trị $k$ sao cho $f_{i-1,k-1}+C(k,j)$ nhỏ nhất, ta cần chứng minh với $l\leq r$ có $opt(l,r)\leq opt(l,r+1)$.
Xét $K=1$ dễ thấy $opt(l,r)=a_{l+\lfloor{\frac{r-l+1}{2}}\rfloor}\leq a_{l+\lfloor{\frac{r-l+2}{2}}\rfloor}=opt(l,r+1)$.
Xét $K=2$ ta chứng minh $opt(l,r)-opt(l,r+1)=\frac{S(l,r)}{r-l+1}-\frac{S(l,r+1)}{r-l+2}=\frac{S(l,r)}{r-l+1}-\frac{S(l,r)+a_{r+1}}{r-l+2}\leq 0$ hay
$S(l,r)(r-l+2)\leq (S(l,r)+a_{r+1})(r-l+1)\Leftrightarrow S(l,r)\leq a_{r+1}(r-l+1)$. Vì $a_i\leq a_{i+1}$ nên $S(l,r)=a_l+a_{l+1}+...+a_r\leq 2a_{l+1}+a_{l+2}+...+a_{r}\leq ...\leq (r-l+1)a_{r+1} \square$.
Từ đây ta dùng được Quy hoạch động chia để trị để tối ưu độ phức tạp xuống $O(ndlog_d)$.
nai0610
Created at
0 likes