算法

(DP) $O(n^4)$

• 我们可以暴力枚举该混合多少材料。
• 由条件可知 $\sum A_i \leqslant X$，枚举在第0时刻混合多少材料，记为 $c$，它们的和 $S$ 与$X$ 在模 $c$ 下同余，理由是 $X$ 是由 $S$ 加了若干个 $c$ 所达到的。
• $dp[i][j][k]$：从前 $i$ 个材料里选取 $j$ 个混合后的魔法药水，其魔力值对 $c$ 取模的结果为 $k$。可以用滚动数组优化掉第一维。

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < int(n); ++i)

using namespace std;
using ll = long long;

void chmax(ll& x, ll y) { if (x < y) x = y; }

ll dp[105][105];

int main() {
    int n;
    ll x;
    cin >> n >> x;

    vector<int> a(n);
    rep(i, n) cin >> a[i];

    ll ans = 1e18;
    const ll INF = 1e18;
    for (int k = 1; k <= n; ++k) {
        rep(i, k + 1)rep(j, k) dp[i][j] = -INF;
        dp[0][0] = 0;
        for (int na : a) {
            for (int i = k - 1; i >= 0; --i) {
                rep(j, k) {
                    chmax(dp[i + 1][(j + na) % k], dp[i][j] + na);
                }
            } 
        }
        ll s = dp[k][x % k];
        if (s >= 0) ans = min(ans, (x - s) / k); 
    }

    cout << ans << '\n';

    return 0;
}