数组划分 - 题目 - 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<>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<>T;while(T--)solve();return 0;
}

 总结：

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

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

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