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
thientruottuyen
Created at
0 likes