Ta gọi ~dp_i~ là số lượng kéo tối đa mà người chơi đầu tiên lấy được khi còn lại ~i~ viên kẹo.

Ta có công thức: ~dp_i = max(A_j + (i - A_j) - dp_{i - A_j})~ với mọi ~1 \leq j \leq n~ và ~A_j \leq i~.

Người chơi thứ nhất có thể lựa chọn lấy ~A_j~ viên kẹo, sau đó là lượt của người chơi thứ 2. Bởi vì cả 2 người đều chơi tối ưu nên người chơi thứ 2 bây giờ giống như người chơi thứ nhất trong lượt của mình, nên số kẹo tối ưu có thể lấy là ~dp_{i - A_j}~.

Còn lại ~(i - A_j) - dp_{i - A_j}~ là số kẹo người chơi thứ hai không thể lấy được, tất cả đều sẽ bị người chơi thứ nhất lấy bởi trong dãy ngoài các số nguyên kia, ta luôn có ~A_1 = 1~.

Độ phức tạp: O(~n \times k~)

Code mẫu

#include <bits/stdc++.h>

using namespace std;

template<class A, class B> bool maximize(A& x, B y) {if (x < y) return x = y, true; else return false;}
template<class A, class B> bool minimize(A& x, B y) {if (x > y) return x = y, true; else return false;}

#define     all(a)                a.begin(), a.end()
#define     pb                    push_back
#define     pf                    push_front
#define     fi                    first
#define     se                    second
// #define     int                   long long

typedef     long long             ll;
typedef     unsigned long long    ull;
typedef     double                db;
typedef     long double           ld;
typedef     pair<db, db>          pdb;
typedef     pair<ld, ld>          pld;
typedef     pair<int, int>        pii;
typedef     pair<ll, ll>          pll;
typedef     pair<ll, int>         plli;
typedef     pair<int, ll>         pill;

const int MAX_N = 100 + 5;
const int MAX_K = 1e5 + 5;

int n, k;
int a[MAX_N];
int dp[MAX_K];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> k >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= k; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[j] <= i) {
                maximize(dp[i], a[j] + (i - a[j]) - dp[i - a[j]]);
            }
        }
    }

    cout << dp[k];

    return 0;
}