Bookshelves

题意

你有 本书，每本书有一个权值 .你要将这 本书分到 个书架上，要求你分组之后的每组权值之和的按位与的值最大。

思路

位运算啊，按位考虑。贪心的从高位到低位的使得此位值为 。我们就可以枚举最后的答案，从大到小，然后依次 一下。我们设计 方程： 。表示在前 个分为了 组是否成立，最后成立条件就是 。

代码

#include<bits/stdc++.h>
#define int long long
const int N=1e3+5,INF=0x3f3f3f3f,mod=998244353;
using namespace std;

int n,k,ans=0;
int w[N],sum[N];
int dp[N][N];

inline int read()
{
    register int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}

int qpow(int a,int b)
{
    int ans=1;
    while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}
    return ans;
}

bool check(int x)
{
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    for(int i=1;i<=k;i++)
     for(int j=1;j<=n;j++)
      for(int m=0;m<j;m++)
       dp[i][j]|=dp[i-1][m]&(((sum[j]-sum[m])&x)==x);
    return dp[k][n];
}

signed main()
{
    n=read();k=read();
    for(int i=1;i<=n;i++)    w[i]=read(),sum[i]=sum[i-1]+w[i];
    for(int i=60;i>=0;i--)
    {
        int mid=ans|(1LL<<i);
        if(check(mid))
            ans|=(1LL<<i);
    }
    printf("%lld",ans);
    return 0;
}