VOJ - ZABAVA

Source: ZABAVA
Tags: Dynamic Programming

Problem:
N sinh viên mới chuẩn bị được nhập vào kí túc xá của trường. Khu kí túc của trường gồm M phòng, mỗi phòng lúc đầu đều không có ai ở. Mỗi ngày có một sinh viên mới sẽ được chuyển vào một trong M phòng này. Khi một người mới đến, buổi tối hôm đó, cả phòng sẽ tổ chức một bữa tiệc để mừng thành viên mới, và họ tạo ra những tiếng ồn, có độ “ồn ào” bằng tổng số người có trong phòng. Trưởng khu kí túc xá không thích điều này, và ông quyết định vào buổi sáng sớm của ngày ông sẽ đuổi hết sinh viên trong một phòng nào đó ra ngoài để tránh sự ồn ào gây ra phiền phức cho ông. Những sinh viên này khi đã bị đuổi thì sẽ ra ngoài kí túc ở và không bao giờ trở lại nữa. Tuy nhiên, trong N ngày, ông chỉ được phép làm việc này K lần. Hãy giúp ông đưa ra những quyết định đúng đắn, để tổng những tiếng “ồn” ông phải chịu là ít nhất có thể.
1 ≤ N ≤ 1e6
1 ≤ M ≤ 100
1 ≤ K ≤ 500

Ví dụ:
Input:
5 1 2
1
1
1
1
1

Output:
7

Explanation:
Sau ngày 1, số sinh viên ở phòng 1 là 1, tổng tiếng ồn đã gây ra là 1.
Sau ngày 2, số sinh viên ở phòng 1 là 2, tổng tiếng ồn đã gây ra là 3.

Sáng đó ông Trưởng khu ký túc xá quyết định hết đám phòng 1 ra ngoài.

Sau ngày 3, số sinh viên ở phòng 1 là 1, tổng tiếng ồn đã gây ra là 4.

Sau ngày 4, số sinh viên ở phòng 1 là 2, tổng tiếng ồn đã gây ra là 6.

Sáng đó ông Trưởng khu ký túc xá quyết định hết đám phòng 1 ra ngoài.

Sau ngày 5, số sinh viên ở phòng 1 là 1, tổng tiếng ồn đã gây ra là 7.

Solution:

Ta nhận thấy được rằng là vấn đề tiếng ồn ở mỗi phòng là riêng biệt và thứ tự ngày có người mới vào phòng đó không quan trọng, ta chỉ cần quan tâm là sau N ngày sẽ có bao nhiêu người có trong phòng đó (nếu không bị đuổi).

Giả sử tại một phòng có X người và có Y lần đuổi, thì đuổi như thế nào để giảm được tối đa tiếng ồn? Ta có, nếu không đuổi, tổng lượng tiếng ồn gây ra sẽ là X * (X + 1) / 2 (tổng từ 1 đến X). Vậy nếu đuổi tại các ngày A[1], A[2], ..., A[Y] (1 ≤ A[1] < A[2] < ... < A[Y] < X) thì ta sẽ có biểu thức như sau:

A[1] * (A[1] + 1) / 2

+ (A[2] - A[1]) * (A[2] - A[1] + 1) / 2

+ ...

+ (A[Y] - A[Y - 1]) * (A[Y] - A[Y - 1] + 1) / 2 

+ (N - A[Y]) * (N - A[Y] + 1) / 2

Nếu đuổi vào ngày A[1], thì trước đó đã có A[1] người trong phòng, sau khi đuổi thì số lượng người về lại 0, do đó khi đuổi vào ngày A[2] ta sẽ có A[2] - A[1] người ở trong phòng, sau khi đuổi ngày cuối cùng, thì còn X - A[Y] người nữa chuyển vào phòng, nên ta tính tiếp số lượng người này.

Bây giờ ta biến chuyển công thức một chút, gọi B[1] = A[1], B[2] = A[2] - A[1], ..., B[Y] = A[Y] - A[Y - 1] và B[Y + 1] = N - A[Y]. Ta có biểu thức mới:

tổng B[i] * (B[i] + 1) / 2 với i = 1 .. Y + 1

= (tổng (B[i] ^ 2) + tổng (B[i])) / 2

= (tổng (B[i] ^ 2) + X) / 2

Bây giờ ta thấy, vì X và 2 là hằng số, nên biểu thức sẽ phụ thuộc vào giá trị tổng (B[i] ^ 2).

Theo bất đẳng thức AM - GM (hoặc còn gọi là bất đẳng thức trung bình cộng và trung bình nhân, hoặc thân thương hơn là bất đẳng thức Cauchy) cho Y + 1 số dương, ta có:

tổng (B[i]) / (Y + 1) ≥ căn bậc Y + 1 của tích (B[i])

(sorry không biết ghi ký hiệu toán học trên blog sao :<)

Dấu "=" xảy ra khi B[1] = B[2] = ... = B[Y] = B[Y + 1].

Nói cách khác, để đạt giá trị min, chia X thành Y + 1 đoạn có số lượng bằng nhau nhất có thể (vì là số nguyên nên không thể bằng nhau tuyệt đối được). Nếu X chia hết cho Y + 1, gọi Z là số lượng của một đoạn, Z = X / (Y + 1), ta có công thức: Z * (Z + 1) / 2 * (Y + 1). Nhưng khổ nỗi nếu X không chia hết cho Y + 1, ta phải xử lý thêm phần dư, vậy để giải quyết, ta chia đều phần dư X % (Y + 1) ra các phần, lúc này công thức chuẩn của ta sẽ là:

Z * (Z + 1) / 2 * (Y + 1 - X % (Y + 1)) 

+ (Z + 1) * (Z + 2) / 2 * (X % (Y + 1))

Rồi vấn đề rắc rối nhất đã xong. Vậy vấn đề là làm thế nào để biết phòng nào đuổi bao nhiêu lần? Ta có thể giải bằng DP đơn giản như sau:

Gọi F[i][j] là số tiếng ồn nhỏ nhất tính từ phòng 1 đến phòng i và tổng số lần đuổi là j. Gọi công thức trên là calc(X, Y), gọi X[i] là tổng số người chuyển đến phòng i. Ta có công thức sau:

F[i][j] = F[i - 1][j - Y] + calc(X[i], Y) với Y = 0 .. j.

Đáp án cuối cùng là F[M][K]. Độ phức tạp O(M * K).

Code:

#include <iostream>

using namespace std;

int n, m, k, cnt[115];

long long f[115][510];

int main() {

    cin >> n >> m >> k;

    for (int x; n--;)

        cin >> x, ++cnt[x];

    for (int i = 1; i <= m; i++)

        for (int j = 0; j <= k; j++) {

            f[i][j] = 1e18;

            for (int x = 0; x <= j; x++) {

                long long a = cnt[i] / (x + 1), b = cnt[i] % (x + 1);

                long long calc = (a + 1) * (a * (x + 1 - b) + (a + 2) * b) / 2ll;

                f[i][j] = min(f[i][j], f[i - 1][j - x] + calc);

            }

        }

    cout << f[m][k];

}