Nhận xét rằng thứ tự sinh viên chuyển vào các phòng theo từng ngày không ảnh huởng đến cách đuổi của ông chủ. Bởi vì ta có thể xử lý sinh viên từng phòng thành cụm các ngày liền nhau cho đến hết các sinh viên phòng đó, rồi mới xử lý cho sinh viên các phòng tiếp theo. Giả sử có 5 phòng thì ta có thể xử lý các sinh viên phòng 1 trước trong những ngày đầu tiên, sau đó mới xử lý các sinh viên phòng 2, 3, 4 và 5.

Do đó, ta chỉ cần lưu lại a[i] là số lượng sinh viên sẽ ghé thăm phòng thứ i, với 1 <= i <= M <= 100.

Gọi F[i][j] là độ ồn tối thiểu để đạt được đối với phòng i với j lần đuổi. Gọi G[i][j] là độ ổn tối thiểu để xử lý i phòng đầu tiên với j lần đuổi. Quy hoạch động đơn giản như sau:

G[i][j] = G[i-1][j-c] + F[i][c] với 2 <= i <= M, 0 <= j <= K, 0 <= c <= j

với cở sở là G[1][j] = F[1][j], 0 <= j <= K.

Cách tính F[i][j]

Xét phòng i có n sinh viên đến và thực hiện j lần đuổi (n = a[i], 0 <= j <= k)

Với j = 0, độ ồn là 1+2+3+...+n = n*(n+1)/2, và n sinh viên là 1 nhóm liên tục ko bị đuổi.

Với j = 1, n sinh viên sẽ bị chia thành 2 nhóm liên tục, lần lượt có n1 và n2 sinh viên liên tục (n = n1+n2). Như trường hợp j = 0, mỗi nhóm liên tục sẽ có độ ồn là P1 = n1*(n1+1)/2 và P2 = n2*(n2+1)/2

Kết quả cần tối ưu: P = P1+P2 = n1*(n1+1)/2 + n2*(n2+1)/2

Dễ thấy P ~ n1^2 + n2^2 đạt min khi n1 == n2.

Từ nhận xét j = 1, nhận thấy cách dùng j lần đuổi tối ưu là chia đều n sinh viên thành k = j+1 nhóm liên tục có lượng sinh viên bằng nhau.

Công thức tính F[i][j] thông qua P(n,k) với n sinh viên và k nhóm sinh viên liên tục

• Số sinh viên 1 nhóm tối thiểu: p = n/k sinh viên
• Số sinh viên còn lại chưa được chia nhóm: y = n-p*k hay y = n%k
• Chia đều y sinh viên dư này vào k nhóm, sure là y < k
• ==> y nhóm có p+1 sinh viên, x = k-y nhóm có p sinh viên

Do đó

F[i][j] = P(n,k) = x * p(p+1)/2 + y * (p+1)(p+2)/2

Độ phức tạp

Độ phức tạp cho bước đọc dữ liệu là O(N)

Độ phức tạp cho bước tính F[i][j] là O(M*K)

Độ phức tạp cho bước tính G[i][j] là O(M*K^2)

Độ phức tạp: O(max(N, M*K^2))