Tóm tắt đề bài

Cho \(m\) thành phố với mức độ ảnh hưởng động đất lần lượt là \(d_1, d_2, \ldots, d_m\). Cần phân bổ tổng cộng \(n\) triệu đô la cho \(m\) thành phố này sao cho mỗi thành phố nhận được một số nguyên dương \(t_i\) triệu đô la và \(\sum_{i=1}^m t_i = n\).
Gọi \(s_i\) là số lượng thành phố nhận được nhiều tiền hơn thành phố \(i\). Sự bất bình của thành phố \(i\) là \(d_i \cdot s_i\).
Yêu cầu: Tìm cách phân bổ \(t_i\) để tổng sự bất bình \(\sum_{i=1}^m (d_i \cdot s_i)\) là nhỏ nhất.

Phân tích

• Nhận xét 1: Để giảm thiểu tổng sự bất bình, những thành phố có \(d_i\) lớn nên có \(s_i\) nhỏ. Điều này có nghĩa là những thành phố bị ảnh hưởng nặng nề nhất nên được ưu tiên nhận nhiều tiền hơn (hoặc bằng) những thành phố bị ảnh hưởng nhẹ hơn.
• Nhận xét 2: Giả sử ta sắp xếp các thành phố theo thứ tự \(d_i\) giảm dần. Khi đó, nếu \(d_1 \ge d_2 \ge \ldots \ge d_m\), ta nên phân bổ tiền sao cho \(t_1 \ge t_2 \ge \ldots \ge t_m\).
• Nhận xét 3: Gọi các giá trị tiền phân bổ khác nhau là \(v_1 > v_2 > \ldots > v_k\). Giả sử có \(c_1\) thành phố nhận \(v_1\), \(c_2\) thành phố nhận \(v_2\), ..., \(c_k\) thành phố nhận \(v_k\).
  • Các thành phố nhận \(v_1\) có \(s_i = 0\).
  • Các thành phố nhận \(v_2\) có \(s_i = c_1\).
  • Các thành phố nhận \(v_3\) có \(s_i = c_1 + c_2\).
  • Tổng quát, các thành phố thuộc nhóm thứ \(j\) có \(s_i = \sum_{p=1}^{j-1} c_p\).
• Cấu trúc hiệu số: Thay vì quản lý trực tiếp \(t_i\), ta có thể đặt \(t_i\) dưới dạng tổng tích lũy. Gọi \(x_i\) là phần tiền chênh lệch mà các thành phố từ \(1\) đến \(i\) đều nhận được thêm so với các thành phố từ \(i+1\) đến \(m\). Cụ thể:
  • \(t_m = x_m\)
  • \(t_{m-1} = x_m + x_{m-1}\)
  • ...
  • \(t_i = \sum_{j=i}^m x_j\)
  • Với \(x_m \ge 1\) và \(x_j \ge 0\) cho \(j < m\).
  • Điều kiện \(\sum t_i = n\) trở thành \(\sum_{i=1}^m (i \cdot x_i) = n\).

Hướng giải quyết

Quy hoạch động

Sắp xếp mảng \(d\) giảm dần: \(d_1 \ge d_2 \ge \ldots \ge d_m\).
Gọi \(f(i, j)\) là tổng sự bất bình nhỏ nhất khi đã xét đến thành phố thứ \(i\) và tổng số tiền đã phân bổ cho các thành phố từ \(1 \dots i\) (theo cách tính chênh lệch) là \(j\).

Tuy nhiên, cách tiếp cận hiệu quả hơn dựa trên mã nguồn AC là:

• Gọi \(f(pos, money)\) là sự bất bình nhỏ nhất khi xét nhóm thành phố từ \(1\) đến \(pos\) với tổng số tiền còn lại là \(money\).
• Tại mỗi bước, ta có hai lựa chọn:
  1. Tăng tất cả \(t_1, \dots, t_{pos}\) lên 1 đơn vị. Việc này tiêu tốn \(pos\) triệu đô và không làm thay đổi \(s_i\) (vì quan hệ lớn hơn giữa các \(t_i\) không đổi).
  2. Chia nhóm: Chọn một vị trí \(i < pos\) để làm ranh giới. Các thành phố từ \(i+1 \dots pos\) sẽ không được tăng tiền thêm nữa, trong khi các thành phố từ \(1 \dots i\) vẫn có thể tăng tiếp. Khi đó, các thành phố \(i+1 \dots pos\) sẽ có \(s = i\) (vì có \(i\) thành phố phía trước nhận nhiều tiền hơn).

Công thức truy hồi:

• Cơ sở: \(f(1, money) = 0\) và \(f(pos, pos) = 0\).
• Sau khi tính xong DP, ta truy vết để tìm lại các giá trị \(x_i\) và từ đó tính ra \(t_i\).

Độ phức tạp

• Thời gian: \(O(m^2 \cdot n)\), với \(m=30, n=10^4\), số trạng thái là \(30 \cdot 10^4\), mỗi trạng thái chuyển trong \(O(m)\). Tổng cộng khoảng \(9 \cdot 10^6\) phép tính, hoàn toàn khả thi.
• Bộ nhớ: \(O(m \cdot n)\) để lưu bảng DP.

Code tham khảo

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define MAX 35
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define FORR(i, b, a) for(int i = (b); i >= (a); i--)

const ll INF = 1e18;

ll m, n;
pll save[MAX];
ll d[MAX], mon[MAX];
ll f[MAX][10001];

// Hàm quy hoạch động có nhớ
ll dp(int pos, int money) {
    if (money < pos) return INF;
    ll &ans = f[pos][money];
    if (ans != -1) return ans;

    // Trường hợp cơ bản: chỉ còn 1 thành phố hoặc tiền vừa đủ chia mỗi tp 1 đồng
    if (pos == 1 || money == pos) return ans = 0;

    // Lựa chọn 1: Tất cả pos thành phố hiện tại đều nhận thêm ít nhất 1 đồng
    ans = dp(pos, money - pos);

    // Lựa chọn 2: Thử ngắt ở vị trí i, các thành phố từ i+1 đến pos dừng lại ở mức tiền này
    ll totalD = 0;
    FORR(i, pos - 1, 1) {
        totalD += d[i + 1];
        ll curr = dp(i, money - pos);
        if (curr != INF) {
            ans = min(ans, curr + totalD * i);
        }
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    if (!(cin >> m >> n)) return 0;
    FOR(i, 1, m) {
        cin >> save[i].first;
        save[i].second = i;
    }
    // Sắp xếp d_i giảm dần
    sort(save + 1, save + 1 + m, greater<pll>());
    FOR(i, 1, m) d[i] = save[i].first;

    memset(f, -1, sizeof(f));

    cout << dp(m, n) << endl;

    // Truy vết
    int currM = m, currN = n;
    while (currM) {
        if (currM == 1) {
            mon[currM] += currN; 
            break;
        }
        mon[currM]++;
        if (currM == currN) break;

        // Kiểm tra xem trạng thái f[currM][currN] đến từ đâu
        if (currN >= currM && f[currM][currN] == f[currM][currN - currM]) {
            currN -= currM;
            continue;
        }

        ll totalD = 0;
        bool found = false;
        FORR(i, currM - 1, 1) {
            totalD += d[i + 1];
            if (f[i][currN - currM] != -1) {
                ll val = f[i][currN - currM] + totalD * i;
                if (val == f[currM][currN]) {
                    currN -= currM;
                    currM = i;
                    found = true;
                    break;
                }
            }
        }
        if (!found) break;
    }

    // Tính t_i từ các bước chênh lệch (prefix sum ngược)
    FORR(i, m - 1, 1) mon[i] += mon[i + 1];

    // Trả lại vị trí ban đầu của các thành phố
    static ll res[MAX];
    FOR(i, 1, m) res[save[i].second] = mon[i];
    FOR(i, 1, m) cout << res[i] << (i == m ? "" : " ");
    cout << endl;

    return 0;
}