题目

思路

• 折半搜索
  • 注意要从小到大排序（虽然我也不知道为什么）

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, t;
int a[35];
unordered_map<ll, int> h;
int ans = INT_MAX;
void dfs1(int k, int cnt, ll sum)
{if(cnt >= ans || sum > m) return;if(sum == m){ans = min(ans, cnt);return;}if(k > t){if(h.count(sum)) h[sum] = min(h[sum], cnt);else h[sum] = cnt;return;}dfs1(k+1,cnt,sum);dfs1(k+1,cnt,sum+a[k]);dfs1(k+1,cnt+1,sum+a[k]/2);
}
void dfs2(int k, int cnt, ll sum)
{if(cnt >= ans || sum > m) return;if(sum == m){ans = min(ans, cnt);return;}if(h.count(m-sum)){ans = min(ans, cnt+h[m-sum]);}if(k > n) return;dfs2(k+1,cnt,sum);dfs2(k+1,cnt,sum+a[k]);dfs2(k+1,cnt+1,sum+a[k]/2);
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cin >> n >> m;m <<= 1;t = n >> 1;for(int i = 1; i <= n; i++)cin >> a[i], a[i] <<= 1;sort(a+1, a+n+1);dfs1(1, 0, 0);dfs2(t+1, 0, 0);ans == INT_MAX ? ans = -1 : ans = ans;cout << ans;
}