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

数组划分 - 题目 - Daimayuan Online Judge

题意：

思路：

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

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

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

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

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

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

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

Code：

#include 
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<
    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<
        if(!check(ans)) ans^=(1ll<
    }
    cout<'\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

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