[NOI2019]序列

梦里梦外; 2021-11-18 01:50 231阅读 0赞

[LOJ3158][] , [Luogu5470][]

从 \\(a\_1\\dots a\_n\\) , \\(b\_1\\dots b\_n\\) 中各选出 \\(K\\) 个数 , 且**至少 \\(L\\) 组**下标在两个数组中都被选择 , 使选出的数**总和**最大  
多组数据 , \\(T ≤ 10 , 1 ≤∑n ≤ 10^6 , 1 ≤ L ≤ K ≤ n ≤ 2 × 10^5 , 1 ≤ a\_i , b\_i ≤ 10^9\\)

考场上写的是 \\(O(n^4)\\) 的 \\(DP\\) , 设 \\(dp\[i\]\[j\]\[k\]\[l\]\\) 为到第 \\(i\\) 位 , 一共选了 \\(j\\) 对 , 其中 \\(a\\) 选了 \\(k\\) 个 , \\(b\\) 选了 \\(l\\) 个的方案数 . 可以过 \\(n<=30\\) , \\(28\\)分 . 再往上开内存就不够了 , 直接编译不了 .

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define debug(...) fprintf(stderr,__VA_ARGS__)
    #define Debug(x) cout<<#x<<"="<<x<<endl
    using namespace std;
    typedef long long LL;
    const int INF=1e9+7;
    inline LL read(){
        register LL x=0,f=1;register char c=getchar();
        while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
        while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();
        return f*x;
    }
    
    const int N = 31;
    
    int a[N], b[N], c[N], d[N], e[N];
    int n, K, L, T;
    
    /*namespace tanxin{
        LL ans = 0;
        inline bool cmp1(int x, int y){
            return a[x] + b[x] > a[y] + b[y];
        }
        inline int solve(){
            ans = 0;
            for(int i = 1; i <= n; ++i) c[i] = i;
            sort(c + 1, c + n + 1, cmp1);
            for(int i = 1; i <= L; ++i) ans += a[c[i]] + b[c[i]];
            for(int i = L + 1; i <= n; ++i) d[i - L] = a[c[i]], e[i - L] = b[c[i]];
            sort(d + 1, d + L + 1); sort(e + 1, e + L + 1);
            for(int i = 1; i <= K - L; ++i) ans += d[i] + e[i];
            printf("%lld\n", ans);
        }
    };*/
    
    namespace baoli_1{
        LL dp[N][N][N][N];
        LL ans;
        inline void chkmax(LL& a, LL b){ if(b > a) a = b; }
        inline void main(){
            memset(dp, -1, sizeof dp);
            dp[0][0][0][0]=0;
            ans = 0;
            for(int i = 0; i <= n - 1; ++i)
            for(int j = 0; j <= K; ++j)
            for(int k = 0; k <= K; ++k)
            for(int l = 0; l <= K; ++l)
            if(~dp[i][j][k][l]){
                chkmax(dp[i+1][j][k][l], dp[i][j][k][l]);
                if(j < K && k < K && l < K) chkmax(dp[i+1][j+1][k+1][l+1], dp[i][j][k][l] + a[i+1] + b[i+1]);
                if(k < K) chkmax(dp[i+1][j][k+1][l], dp[i][j][k][l] + a[i+1]);
                if(l < K) chkmax(dp[i+1][j][k][l+1], dp[i][j][k][l] + b[i+1]);
            }
            for(int i = L; i <= K; ++i) 
                chkmax(ans, dp[n][i][K][K]);
            printf("%lld\n", ans);
        }
    };
    
    int main(){
    #ifndef file
        freopen("sequence.in","r",stdin);
        freopen("sequence.out","w",stdout);
    #endif
        T = read();
        while(T--){
            n = read(), K = read(), L = read();
            for(int i = 1; i <= n; ++i) a[i] = read();
            for(int i = 1; i <= n; ++i) b[i] = read();
            //tanxin::solve();
            if(n <= 150) baoli_1::main();
        }
    }

然后我又到 \\(LOJ\\) 上找了一个[优秀的做法][Link 1].  
总体思路是**先选出 \\(K-L\\) 组下标不同的 , 再选出 \\(L\\) 组下标相同的** .

先选出 \\(K-L\\) 组下标不同的 , 就直接在 \\(a\\) 和 \\(b\\) 中选出最大的 \\(K-L\\) 个 , 再选出剩下 \\(L\\) 对  
如果第一阶段选出了下标相同的 , 就记下选了 \\(cnt\\) 对 , 第二阶段中有 \\(cnt\\) 次可以不选相同的 , 这样就能保证**至少选了 \\(L\\) 组相同的** . 此时也就是没有限制 , 直接选出 \\(a\\) 和 \\(b\\) 中最大的即可 .

再选出 \\(L\\) 对 , 有三种选法 : 选出 \\(a+b\\) 最大的 ; 已经选了 \\(a\\) 中的 \\(b\\) 最大的 + \\(a\\) 最大的 ; 已经选了 \\(b\\) 中的 \\(a\\) 最大的 + \\(b\\) 最大的 . **要用几个堆维护这些下标 , 还要记录每个下标被选的状态 , 并及时更新 .** 对于没取满的状态要及时放入该放的堆里 , 对于取满的状态**如果是第一阶段**要更新 \\(cnt\\) .

由于要用堆维护"贪心"的下标 , 时间复杂度是 \\(O(n\\log n)\\) , \\(n\\) 为 \\(\\sum n = 10^6\\) .  
本题难点已经加粗 , 具体细节见代码

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #include<queue>
    #define debug(...) fprintf(stderr,__VA_ARGS__)
    #define Debug(x) cout<<#x<<"="<<x<<endl
    using namespace std;
    typedef long long LL;
    const int INF=1e9+7;
    inline LL read(){
        register LL x=0,f=1;register char c=getchar();
        while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
        while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();
        return f*x;
    }
    
    const int N = 1e6 + 5;
    
    int a[N], b[N], op[N];
    bool visa[N], visb[N];
    int T, n, K, L, cnt;
    
    struct Rank_a{ inline bool operator()(int& x, int& y){return a[x] < a[y];} };
    struct Rank_b{ inline bool operator()(int& x, int& y){return b[x] < b[y];} };
    struct Rank_ab{ inline bool operator()(int& x, int& y){return a[x]+b[x] < a[y]+b[y];} };
    priority_queue <int, vector<int>, Rank_a> qa,qA;
    priority_queue <int, vector<int>, Rank_b> qb,qB;
    priority_queue <int, vector<int>, Rank_ab> qC;
    
    inline void update(int x){
        if(op[x] == 0) qC.push(x); // 一开始没被选的可以当做一对被选
        if(op[x] == 1) qB.push(x);
        if(op[x] == 2) qA.push(x);
        if(op[x] == 3) cnt++;
    }
    
    int main(){
        freopen("sequence.in", "r", stdin);
        freopen("sequence.out", "w", stdout);
        T = read();
        while(T--){
            LL ans = 0; cnt = 0;
            while(qa.size()) qa.pop();
            while(qb.size()) qb.pop();
            while(qA.size()) qA.pop();
            while(qB.size()) qB.pop();
            while(qC.size()) qC.pop();
    
            n = read(), K = read(), L = read();
            for(int i = 1; i <= n; ++i) a[i] = read(), qa.push(i);
            for(int i = 1; i <= n; ++i) b[i] = read(), qb.push(i);
            for(int i = 1; i <= n; ++i) visa[i] = visb[i] = op[i] = 0;
    
            for(int i = 1; i <= K - L; ++i){
                int pa = qa.top(); qa.pop(), visa[pa] = 1, op[pa] |= 1;
                int pb = qb.top(); qb.pop(), visb[pb] = 1, op[pb] |= 2;
                ans += a[pa] + b[pb];
            }
    
            for(int i = 1; i <= n; ++i) update(i);
            for(int i = 1; i <= L; ++i){ // 接下来L组都要取相同的
                while(visa[qa.top()] == 1) qa.pop();
                while(visb[qb.top()] == 1) qb.pop();
                while((!qA.empty()) && (op[qA.top()] != 2)) qA.pop();
                while((!qB.empty()) && (op[qB.top()] != 1)) qB.pop();
                while((!qC.empty()) && (op[qC.top()] != 0)) qC.pop();
                if(cnt){ // 如果能保证取到当前的任务,那就不是必须取相同的
                    int pa = qa.top(); qa.pop(), visa[pa] = 1, op[pa] |= 1;
                    int pb = qb.top(); qb.pop(), visb[pb] = 1, op[pb] |= 2;
                    ans += a[pa] + b[pb];
                    -- cnt;
                    update(pa); // 一定要及时更新
                    if(pa^pb) update(pb); // 有可能选了两个下标相同的,最后只更新一次
                }
                else{ // 取相同的
                    int type = -1, tmax = 0, tmp;
                    if((!qA.empty()) && (!qb.empty()) && ((tmp = a[qA.top()] + b[qb.top()]) > tmax)) type = 1, tmax = tmp;
                    if((!qB.empty()) && (!qa.empty()) && ((tmp = a[qa.top()] + b[qB.top()]) > tmax)) type = 2, tmax = tmp;
                    if((!qC.empty()) && ((tmp = a[qC.top()] + b[qC.top()]) > tmax)) type = 3, tmax = tmp;
                    ans += tmax; ///
                    if(type == 1){
                        int pa = qA.top(); qA.pop(), visa[pa] = 1, op[pa] |= 1;
                        int pb = qb.top(); qb.pop(), visb[pb] = 1, op[pb] |= 2, update(pb);
                    }
                    if(type == 2){
                        int pa = qa.top(); qa.pop(), visa[pa] = 1, op[pa] |= 1, update(pa);
                        int pb = qB.top(); qB.pop(), visb[pb] = 1, op[pb] |= 2;
                    }
                    if(type == 3){
                        int pc = qC.top(); qC.pop(), visa[pc] = visb[pc] = 1, op[pc] = 3;
                        // 就是要取这一对,不用再update更新cnt
                    }
                }
            }
            printf("%lld\n", ans);
        }
    }

转载于:https://www.cnblogs.com/lizehon/p/11211100.html

[LOJ3158]: https://loj.ac/problem/3158
[Luogu5470]: https://www.luogu.org/problemnew/show/P5470
[Link 1]: https://loj.ac/submission/530602