Đâ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(ndlogd)$.
Lời giải bài toán: Chi phí nhỏ nhất
Đề bài tóm tắt
Cho một dãy số không giảm $a_1, a_2, ..., a_n.$ Ta cần chia dãy này thành d đoạn liên tiếp, sao cho tổng chi phí nhỏ nhất.
Chi phí của một đoạn từ chỉ số l đến r được định nghĩa là:
$min_{z ∈ Z} ∑_{i=l}^r |a_i - z|^k$
Với $k ∈ {1, 2}$.
Yêu cầu: Tính tổng chi phí nhỏ nhất khi chia thành đúng d đoạn.
Phân tích chi phí đoạn
- Với k = 1: Biểu thức tối ưu đạt được khi z là median của dãy con $a_l, ..., a_r.$
- Với k = 2: Biểu thức tối ưu đạt được khi z là mean (trung bình cộng). Tuy nhiên, do z phải là số nguyên, ta cần xét cả floor(mean) và ceil(mean), chọn giá trị nào cho chi phí nhỏ hơn.
- Với k = 1, chỉ cần tìm median và tính tổng giá trị tuyệt đối.
+ với $pre[i]$ là tổng tiền tố đến vị trí thứ i thì ta có thể suy ra
+ Cost(i, mid) = $∑_{i=l}^r |a_i - a[mid]|^1$
=> $Cost(i, j) = (a[mid]) \times (mid - i + 1) - (pre[mid] - pre[i - 1]) + (pre[j] - pre[mid- 1]) - (a[mid]) \times (j - mid + 1) $
- Với k = 2, dùng prefix sum và prefix square sum để tính chi phí khi chọn z = floor(mean) và z = ceil(mean). suy ra từ hằng đẳng thức số 2
Cost(i, mid) = $∑_{i=l}^r |a_i - tbc|^2$
sau khi khai triển hdt số 2 ta thu được
+ suy ra $Cost(i, j) = cur - 2 \times (pre[j] - pre[i - 1]) \times tbc + tbc \times tbc \times (j - i + 1)$;
(với cur là prefix square sum trong đoạn (i j), tbc là trung bình cộng của đoạn (i j))
Quy hoạch động
Gọi $dp[i][j]$ là chi phí nhỏ nhất để chia i phần tử đầu tiên thành j đoạn.
Công thức quy hoạch động:
$dp[i][j] = min_{p < i} (dp[p][j - 1] + cost[p+1][i])$
Khởi tạo: $dp[0][0]$ = 0,Các giá trị còn lại khởi tạo bằng vô cùng, Kết quả cuối cùng là $dp[n][d]$.
ta có thể tối ưu bằng dp kết hợp chia để trị
Độ phức tạp $ O(n\times log2(n) \times d)$
Kết luận
Bài toán yêu cầu tối ưu hóa chi phí theo từng đoạn, trong đó mỗi đoạn có chi phí nhỏ nhất nếu chọn giá trị đại diện z hợp lý (median hoặc mean). Việc áp dụng quy hoạch động kết hợp tiền xử lý chi phí từng đoạn giúp giải quyết hiệu quả bài toán trong thời gian chấp nhận được.
code c++ : https://ideone.com/AEs4nJ
nai0610
Created at
2 likes
thientruottuyen
Created at
0 likes