1 条题解

  • 0
    @ 2024-6-4 15:26:11

    题意很绕,但实际上很简单。

    首先,我们可以用dpi,jdp_{i,j}来求出,使用第ii种龙珠的碎片,能否拼凑出恰好为jj能量的龙珠,这个复杂度是O(xim)O(∑x_im)的。

    接下来的问题,就变成如下内容了:

    你有77个数组,每个数组里有若干个数字,你需要从77个数组里面各挑一个数字出来,把他们的和作为这次挑出数字的代价。

    问:你能挑出来的第k105k\leq 10^5大的数字是多少。

    我们称(a,b,c,d,e,f,g)(a,b,c,d,e,f,g)为从第11个数组里挑第aa大的,第22个数组里挑第bb大的,...的方案。

    那么,全局最大必定是(1,1,1,1,1,1,1)(1,1,1,1,1,1,1),我们把它丢进优先队列里去。

    那么谁可能是第二大的呢?必然是$(2,1,1,1,1,1,1),(1,2,1,1,1,1,1,1),(1,1,2,1,1,1,1,1),...$中的一项。

    因此我们把这77种可能丢进优先队列里去,下次拿出来价值最大的方案即可。

    一共需要取出kk次,那么最多丢进去7k7k个元素,复杂度O(7klog7k)O(7klog {7k})。需要注意不要丢重复元素进去哈。

    看起来7e97e9的复杂度,但实际上因为dp的过程常数非常小,可以通过。

    一个彩蛋是,这个dp可以通过bitset优化到xim64\sum{\frac{x_im}{64}}

    #pragma GCC optimize("Ofast")
    #include <bits/stdc++.h>
    #define N 100005
    #define M 100005
    #define int long long
    using namespace std;
    inline int rd() {
        int X = 0, w = 0;
        char ch = getchar();
        while (!isdigit(ch)) {
            w |= ch == '-';
            ch = getchar();
        }
        while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
        return w ? -X : X;
    }
    int m, k, a[N], b[8];
    bool dp[2][M];
    int q[8][M], top[8];
    void work(int id) {
        int n = rd();
        for (int i = 1; i <= n; ++i) a[i] = rd();
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        // cout<<n*m<<endl;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= m; ++j) dp[i & 1][j] |= dp[(i & 1) ^ 1][j];
            for (int j = a[i]; j <= m; ++j) dp[i & 1][j] |= dp[(i & 1) ^ 1][j - a[i]];
        }
        for (int i = 0; i <= m; ++i)
            if (dp[n & 1][i])
                q[id][++top[id]] = i * b[id];
        sort(q[id] + 1, q[id] + 1 + top[id]);
    }
    struct nod {
        int id[8], val;
        bool operator<(nod u) const {
            if (val != u.val)
                return val < u.val;
            for (int i = 1; i <= 7; ++i)
                if (id[i] != u.id[i])
                    return id[i] < u.id[i];
            return 0;
        }
    } ans[N], nxt;
    priority_queue<nod> Q;
    map<nod, bool> mp;
    signed main() {
        // freopen("dragon.in","r",stdin);
        // freopen("dragon.out","w",stdout);
        m = rd(), k = rd();
        for (int i = 1; i <= 7; ++i) b[i] = rd();
        for (int i = 1; i <= 7; ++i) work(i);
    
        nxt.val = 0;
        for (int i = 1; i <= 7; ++i) nxt.id[i] = top[i], nxt.val += q[i][top[i]];
        mp[nxt] = 1;
        Q.push(nxt);
        for (int i = 1; i <= k; ++i) {
            if (Q.empty()) {
                puts("Stop dreaming XJC!");
                return 0;
            }
            ans[i] = Q.top();
            Q.pop();
            for (int t = 1; t <= 7; ++t)
                if (ans[i].id[t] > 1) {
                    nxt = ans[i];
                    nxt.id[t]--;
                    nxt.val += q[t][nxt.id[t]] - q[t][nxt.id[t] + 1];
                    if (mp.count(nxt))
                        continue;
                    mp[nxt] = 1;
                    Q.push(nxt);
                }
        }
        // for(int i=1;i<=k;++i){
        // 	cout<<ans[i].val<<'\n';
        // 	for(int t=1;t<=7;++t) cout<<q[t][ans[i].id[t]]<<' ';cout<<'\n';
        // }
        cout << ans[k].val << endl;
    }
    
    • 1

    信息

    ID
    1419
    时间
    3000ms
    内存
    512MiB
    难度
    9
    标签
    (无)
    递交数
    110
    已通过
    11
    上传者