代码源每日一题div1 DP 数组划分

向右看齐 2024-03-31 13:09 17阅读 0赞

[数组划分 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge]

题意：

![3df804eb4f5b44eba55fd2e37025d777.png][]

思路：

关于位运算的最大值，只需要按位去贪心即可，即从高位向低位贪心，答案一定是1111000的形式

那么我们去枚举这个1和0的分界线在哪就好了

对于一个确定好的分界线，去check一下这个答案是否能够满足条件

本来考虑在check里面进行贪心，但是贪心未遂，因此可以在check里面dp

状态设计：dp\[i\]\[j\]，表示前i个数，划分了j段的每段和的与的最大值

确定好状态含义后，我们去枚举上一个状态

首先去枚举第j段的长度，第j段长度确定后，如果第j段满足条件（即第j段的和比答案大），就去枚举上一段（第j-1段)的长度，取上一个状态的最大值就行（最优子结构）

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define low(x) (x&-x)
    #define mnf 0x3f3f3f3f
    #define inf 0xc0c0c0c0
    #define rep(i,x,y) for(int i=x;i<=y;i++)
    #define pre(i,x,y) for(int i=x;i>=y;i--)
    #define int long long
    const int mxn=1e2+10,mxv=1e6+10;
    int n,k,ans=0;
    int a[mxn],dp[mxn][mxn],pre[mxn];
    bool check(int x){
        //cout<<x<<'\n';
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;
        rep(i,1,n){
            rep(j,1,i){
                if(((pre[i]-pre[j-1])&x)==x){
                    rep(len,1,k) dp[i][len]|=dp[j-1][len-1];
                }
            }
        }
        return dp[n][k];
    }
    void solve(){
        ans=0;
        cin>>n>>k;
        rep(i,1,n) cin>>a[i];
        rep(i,1,n) pre[i]=pre[i-1]+a[i];
        pre(i,60,0){
            ans|=(1ll<<i);
            if(!check(ans)) ans^=(1ll<<i);
        }
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int T=1;
        //cin>>T;
        while(T--)solve();
        return 0;
    }

**总结：**

**关于的位运算贪心，一般考虑按位贪心**

**如果在check函数里面不能贪心，就去考虑dp**

**考虑状态转移时，可以考虑枚举决策，或者直接枚举上一个状态**

[- _ - Daimayuan Online Judge]: http://oj.daimayuan.top/problem/665
[3df804eb4f5b44eba55fd2e37025d777.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/bd74eaf3b4894c1599b6876130d004ca.png