[ural 2123]. Knapsack

题意

有\(n\)种物品，每种有2个，且每种有重量\(a_i\)，并且保证\(a_i \geq a_{i - 1} * 2\)。
问从中任意取，有多少种方案能使重量和为\(W\)。
\(n \leq 60, a_i \leq {10} ^ {18}, W \leq 4 * {10} ^ {18}\)。

题解

一个暴力剪枝就过了。复杂度？暂时没有想到证明。

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int N = 65;
ll n, W, a[N], s[N];
map <ll, ll> f, g;
int main () {
    cin >> n >> W, f[W] = 1;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        s[i] = s[i - 1] + a[i] * 2;
    }
    for (int i = n; i; --i) {
        g.clear();
        for (auto p : f) {
            if (a[i] * 2 <= p.fi && s[i - 1] + a[i] * 2 >= p.fi) {
                g[p.fi - a[i] * 2] += p.se;
            }
            if (a[i] <= p.fi && s[i - 1] + a[i] >= p.fi) {
                g[p.fi - a[i]] += p.se;
            }
            if (s[i - 1] >= p.fi) {
                g[p.fi] += p.se;
            }
        }
        f = g;
    }
    cout << f[0] << endl;
    return 0;
}

[ural 2123]. Knapsack

原文：https://www.cnblogs.com/psimonw/p/11795367.html