• 【代码源每日一题Div1】#665. 数组划分「位运算贪心+动态规划」


    #665. 数组划分

    题目描述:

    给你n个整数,将其划分为恰好k个子数组,求对每个子数组求和后按与运算的最大值

    思路:

    这个题和之前写过的一个最小或运算生成树类似,那个题的思路是从高位开始枚举二进制的每一位i,看在上一次能选的边的情况下,不选第i位为1的边后,看能不能构成一颗生成树,如果可以构成,则最小生成树的值的第i位是0,然后把所有边权在第i位是1的边给删掉

    这个题也类似,根据贪心的思路,显然二进制高位的优先选

    但是这个题的处理方式和那个不太一样,那个题可以通过删边来解除不需要选的高位产生的影响,而我们这个题不能删边,所以可以换一种方法:

    首先我们写一个函数叫check(x),来判断n个数字能否分出k个子数组,使得每个子数组求和以后进行与运算的值是x

    假设在此之前已经得到的答案为x,则我们只需要去check一下 x + 2 i x+2^i x+2i即可判断第i位是否可取

    所以我们现在需要做的是写一个check函数

    check的方法是dp

    开一个bool类型的dp数组,dp[i][len]表示前i个数字,是否存在len个子数组的和进行与运算后得到x

    显然i是第len个子数组的最后一个元素,我们可以枚举一下这个子数组的左边界j,如果 ( ( ∑ p = j i a r [ p ] ) ((\sum_{p=j}^{i}ar[p]) ((p=jiar[p])& x ) = = x x) == x x)==x则是说明可以进行转移,我们就让dp[i][len] |= dp[j][len-1]

    判断一下dp[n][k]即可

    #include
    using namespace std;
    #define int long long
    #define endl '\n'
    #define io ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
    #define m_p(a,b) make_pair(a, b)
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    #define MAX 300050
    
    int n, m, k, x;
    ll tr[MAX];
    ll sum[MAX];
    
    ll cal(int l, int r){
        return sum[r] - sum[l - 1];
    }
    bool dp[105][105];
    bool check(ll x){
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= i; ++j){
                if((cal(j, i)&x) == x){
                    for(int len = 1; len <= k; ++len){
                        dp[i][len] |= dp[j-1][len-1];
                    }
                }
            }
        }
        return dp[n][k];
    }
    
    void work(){
        cin >> n >> k;
        for(int i = 1; i <= n; ++i)cin>>tr[i];
        for(int i = 1; i <= n; ++i)sum[i] = sum[i-1]+tr[i];
        ll ans = 0;
        for(int i = 60; i >= 0; --i){
            ans |= (1ll<<i);
            if(!check(ans))ans -= (1ll<<i);
        }
        cout << ans << endl;
    }
    
    signed main(){
        work();
        return 0;
    }
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
  • 相关阅读:
    EXCEL VBA 入门与实用例子
    B站:李宏毅2020机器学习笔记 5 —— 分类器Classification
    Flutter 第一个程序Hello World!
    PTA 7-195 列出M的N次乘方表
    SpringFramework 之EnableCaching
    Jellyfish and Mex
    java计算机毕业设计ssm健达企业项目管理系统
    mysql case when 不命中缓存
    算法通关村第二关-青铜终于学会链表了
    nginx中用到的kill命令
  • 原文地址:https://blog.csdn.net/weixin_51216553/article/details/128023900