暴力三维DP容易想到

也容易想到贪心每一位，尽量不选

但是怎么check呢？又是拼起来

f[i][j]表示枚举到第i位，分成j组，且可以满足当前假设是否有可行解

转移不难自己看代码吧

但是这样是O(logm*n^3)的，subtest5过不去

但是它又有一个A==1，就可以维护枚举到第i位分成组数最小的方案数

好题啊！

#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>using namespace std;typedef long long LL;const int sbt4_maxn=1e2+10;const int sbt5_maxn=2*1e3+10;int n,A,B;LL s[sbt5_maxn],ans;int g[sbt5_maxn];bool check1(int p){ memset(g,63,sizeof(g));g[0]=0; for(int i=0;i<n;i++) if(g[i]!=g[sbt5_maxn-1]) for(int k=i+1;k<=n;k++) if( !((s[k]-s[i])&(1LL<<p)) && ( ((s[k]-s[i])|ans)^ans )<=(1LL<<p+1)-1 ) g[k]=min(g[k],g[i]+1); return g[n]<=B;}bool f[sbt4_maxn][sbt4_maxn];bool check2(int p){ memset(f,false,sizeof(f));f[0][0]=true; for(int i=0;i<n;i++) for(int j=0;j<B;j++) if(f[i][j]) for(int k=i+1;k<=n;k++) if( !((s[k]-s[i])&(1LL<<p)) && ( ((s[k]-s[i])|ans)^ans )<=(1LL<<p+1)-1 ) f[k][j+1]=true; for(int j=A;j<=B;j++) if(f[n][j])return true; return false;}int main(){ freopen("a.in","r",stdin); freopen("a.out","w",stdout); int mb=0; scanf("%d%d%d",&n,&A,&B); for(int i=1;i<=n;i++) { scanf("%lld",&s[i]),s[i]+=s[i-1]; for(int j=62;j>=0;j--) if(s[i]&(1LL<<j)){mb=max(mb,j);break;} } ans=0; for(int i=mb;i>=0;i--) if(A==1) { if(!check1(i))ans|=(1LL<<i); } else { if(!check2(i))ans|=(1LL<<i); } printf("%lld\n",ans); return 0;}