算法
(折半搜索) $O(2^{\frac{n}{2}}*n)$
直接折半搜索即可。
三倍经验:
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main() {
int n, T;
cin >> n >> T;
vector<int> a(n);
rep(i, n) cin >> a[i];
vector<ll> s(1), t(1);
rep(i, n) {
for (int j = s.size()-1; j >= 0; --j) {
ll now = s[j]+a[i];
if (now <= T) s.push_back(now);
}
swap(s, t);
}
sort(s.begin(), s.end());
ll ans = 0;
for (ll x : t) {
int si = upper_bound(s.begin(), s.end(), T - x) - s.begin();
ans = max(ans, x + s[si - 1]);
}
cout << ans << '\n';
return 0;
}