Gym – 101102A A. Coins 背包问题、数学

Source

2016 ACM Amman Collegiate Programming Contest

UESTC 2017 Winter Training #1

Gym - 101102A

My Solution

题意：在a中选一个子集b中选一个子集，使它们的和为w且abs(sumai - sumbi) <= k，问方案数。

背包问题、数学
w = sumai +sumbi，da[j]表示a构出和为j时的方案数，db[j]为构出和为j时的方案数。
故枚举可能的sumai，然后对应w - sumai，则ans = sigma(da[sumai] * db[w - sumai])
然后求da，db的方法是01背包，
复杂度 O(n*w)

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 1.5e4 + 8;

int a[158], b[158];
LL da[maxn], db[maxn], l, r, ans;


const LL MOD = 1e9 + 7;

inline LL mod(const LL &x)
{
    return x - x / MOD * MOD;
}

int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    //freopen("a.out", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    int T, n, m, k, w, i, j;
    cin >> T;
    while(T--){
        memset(da, 0, sizeof da); memset(db, 0, sizeof db);

        cin >> n >> m >> k >> w;
        if((w + k) & 1){
            l = (w - k) / 2 + 1, r  = (w + k) / 2;
        }
        else{
            l = (w - k) / 2, r  = (w + k) / 2;
        }
        for(i = 0; i < n; i++){ cin >> a[i];
        }
        da[0] = 1;
        for(i = 0; i < n; i++){ for(j = w; j >= 0; j--){
                if(j - a[i] >= 0) da[j] = mod(da[j] + da[j - a[i]]);
                else break;
            }
        }

        for(i = 0; i < m; i++){ cin >> b[i];
        }
        db[0] = 1;
        for(i = 0; i < m; i++){ for(j = w; j >= 0; j--){
                if(j - b[i] >= 0) db[j] = mod(db[j] + db[j - b[i]]);
                else break;
            }
        }

        ans = 0;
        for(i = l; i <= r; i++){
               // cout << da[i] << " " << db[i] << endl;
            ans = mod(ans + mod(da[i] * db[w - i]));
        }

        cout << ans << endl;

    }
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx