题目描述

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