题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxN = 20, halfN = 10;
int n,mid,ans, a[maxN];
bitset<1 << halfN> vis[1 << halfN];
map<int, bitset<1 << halfN>> mp;
void ldfs(int k, int cost, int id) {
if (k ==mid) {
mp[cost].set(id);
return;
}
ldfs(k + 1, cost, id);
ldfs(k + 1, cost + a[k], id | (1 << k));
ldfs(k + 1, cost - a[k], id | (1 << k));
}
void hdfs(int k, int cost, int id) {
if (k == n) {
if (mp.count(cost))
{
bitset<1 << halfN> s(mp[cost]);
s &= ~vis[id];
ans += s.count();
vis[id] |= s;
}
return;
}
hdfs(k + 1, cost, id);
hdfs(k + 1, cost + a[k], id | (1 << k-mid));
hdfs(k + 1, cost - a[k], id | (1 << k-mid));
}
int main() {
cin >> n; mid = n >> 1;
for (int i = 0; i < n; ++i)
cin >> a[i];
sort(a, a + n);//加了更快
ldfs(0, 0, 0);
hdfs(mid, 0, 0);
cout << ans - (1) ;//去除两个都为0的情况所以减1
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla