Hướng dẫn giải của Chia tiền thưởng

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Subtask 1

Sử dụng if-else để liệt kê các khả năng có thể xảy ra.

  • Cả An và Bình không lấy tờ tiền nào.
  • An lấy tờ tiền thứ nhất, Bình lấy tờ tiền thứ hai.
  • An lấy tờ tiền thứ nhất, Bình lấy tờ tiền thứ hai và ba.
  • An lấy tờ tiền thứ hai, Bình lấy tờ tiền thứ nhất. ...

Kiểm tra tất cả các trường hợp và với mỗi trường hợp, kiểm tra xem số tiền An và Bình nắm giữ có bằng nhau không.

Subtask 2

Với mỗi tờ tiền, có ~3~ khả năng có thể xảy ra: An giữ, Bình giữ hoặc được đem đi đầu tư. Ta có thể duyệt qua ~3^n~ khả năng để tìm ra phương án tối ưu nhất sử dụng quay lui.

Code tham khảo C++

int n, a[15];
int res = 0;

void ql(int i, int An, int Binh){
    if (i == n + 1){
        if (An == Binh) res = max(res, An);
        return;
    }

    ql(i + 1, An + a[i], Binh); // An giữ tờ tiến thứ i
    ql(i + 1, An, Binh + a[i]); // Bình giữ tờ tiền thứ i
    ql(i + 1, An, Binh); // tờ tiền được đem đi đầu tư
}

Subtask 3

Subtask này ta sẽ sử dụng quy hoạch động.

Gọi ~f[i][diff]~ là lượng tiền đem đi đầu tư ít nhất khi xét đến tờ thứ ~i~ và lượng tiền chênh lệch giữa An và Bình là ~diff~.

Tương tự, vẫn có ~3~ trường hợp có thể xảy ra với tờ tiền thứ ~i~:

  • An giữ: ~f[i][diff] = f[i - 1][diff - a[i]]~
  • Bình giữ: ~f[i][diff] = f[i - 1][diff + a[i]]~.
  • Đem đi đầu tư: ~f[i][diff] = f[i - 1][diff] + a[i]~.

Giá trị của ~f[i][diff]~ là min của 3 trường hợp trên.

Gọi ~sum~ là tổng giá trị của ~n~ tờ tiền. Đáp án bài toán sẽ là ~\frac{sum - f[n][0]}{2}~

Lưu ý:
  • Giá trị của ~diff~ có thể âm ~(-10^5 \le diff \le 10^5)~ nên ta cần cộng thêm biến ~diff~ một lượng ~base~ là ~10^5~ để tránh truy cập vào mảng có index âm.
  • Việc lưu mảng ~f[i][diff]~ cần dùng đến ~500 \times 10^5 \times 2 = 10^8~ int nên sẽ gây tràn bộ nhớ (MLE). Để ý rằng giá trị của ~f[i]~ chỉ dựa vào các ~f[i - 1]~ nên ta chỉ cần duy tri trạng thái của vị trí hiện tại ~i~ và vị trí trước đấy ~i-1~ và cập nhật lần lượt sau khi xét đến vị trí ~i + 1~.

Code tham khảo C++

#include <bits/stdc++.h>
#define ii pair<int, int>
#define st first
#define nd second
#define endl "\n"
#define all(v) v.begin(), v.end()
#define Unique(v) v.erase(unique(all(v)), v.end())

using namespace std;
const int oo = 1e9;

const int base = 1e5;
const int maxw = 1e5 + 5;
const int maxn = 505;

int n, a[maxn];
int dp[2][maxw + base];

void PROGRAM(int _){
    cin >> n;

    for (int i = 1; i <= n; i++) cin >> a[i];

    int sum = accumulate(a + 1, a + n + 1, 0ll);


    for (int weight = 0; weight <= base * 2; weight++){
        dp[0][weight] = oo;
        dp[1][weight] = oo;
    }

    dp[0][base] = 0;

    for (int i = 1; i <= n; i++){
        for (int w = 0; w <= base * 2; w++){
            if (w + a[i] <= base * 2) dp[1][w] = min(dp[1][w], dp[0][w + a[i]]);
            if (w - a[i] >= 0) dp[1][w] = min(dp[1][w], dp[0][w - a[i]]);
            dp[1][w] = min(dp[1][w], dp[0][w] + a[i]);
        }
        for (int w = 0; w <= base * 2; w++){
            dp[0][w] = dp[1][w];
            dp[1][w] = oo;
        }
    }

    cout << (sum - dp[0][base]) / 2;

}

signed main(){
    freopen("CT.INP", "r", stdin);
    freopen("CT.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int test = 1;

    for (int _ = 1; _ <= test; _++){
        PROGRAM(_);
    }

    return 0;
}