买瓜 题解

· · 题解

显然对于每个瓜都有三种状态，买、不买和买一半，因此可以 \mathrm O(3^n) 爆搜，由于这题 n\le 30，显然会超时，所以可以考虑 meet in the middle 算法。将数组平分成两部分分别搜索，最后看能否拼成重量为 m 的瓜即可，时间复杂度 \mathrm O(3^{\frac n2})。

搜索时判断如果重量已经大于 m，或者劈瓜个数大于当前答案就退出。

这题 n\le 30，3^{\frac n2}\le 14348907，用 unordered_map 会 TLE，__gnu_pbds::gp_hash_table 会 MLE+TLE，所以只能自己手写哈希表。

#include<iostream>
#include<algorithm>
using namespace std;

int head[10000005], ky[15000005], nxt[15000005], ccc;
short v[15000005];
const int mod = 9998777;

// 哈希表
void ins(int k, int c)
{
    int id = k%mod;
    ++ccc;
    v[ccc] = c;
    ky[ccc] = k;
    nxt[ccc] = head[id];
    head[id] = ccc;
}
int fd(int x)
{
    if(x < 0) return -1;
    for(int i = head[x%mod]; i; i = nxt[i])
    {
        if(ky[i] == x) return i;
    }
    return -1;
}

// 搜索
int a[35], m, ans = 55;
void dfs(int i, int c, int n, short t)
{
    if(c > m) return;
    if(i > n) {
        int f = fd(c);
        if(f == -1) ins(c, t);
        else v[f] = min(v[f], t);
    }
    else {
        dfs(i+1, c, n, t);
        dfs(i+1, c+a[i], n, t);
        dfs(i+1, c+a[i]/2, n, t+1);
    }
}
void dfs2(int i, int c, int n, short t)
{
    if(c > m || t > ans) return;
    if(i > n)
    {
        int f = fd(m-c);
        if(f != -1) ans = min(ans, v[f]+t);
        return;
    } else {
        dfs2(i+1, c, n, t);
        dfs2(i+1, c+a[i], n, t);
        dfs2(i+1, c+a[i]/2, n, t+1);
    }
}
int main()
{
    int n;
    cin >> n >> m;
    m *= 2;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        a[i] *= 2;
    }
    if(n == 1)
    {
        if(a[1] == m) cout << 0;
        else if(a[1]>>1 == m) cout << 1;
        else cout << -1;
        return 0;
    }
    sort(a+1, a+n+1, [](int a, int b)->bool{return a>b;});
    dfs(1, 0, n/2, 0);
    dfs2(n/2+1, 0, n, 0);
    cout << (ans!=55?ans:-1);
    return 0;
}