Bookshelves

Bookshelves

题意

有本书，每一本书都有一个价值,现在在不改变书的顺序的条件下，把这本书分成段，设每一段的价值之和为 ，问sum [ 1 ] & sum [ 2 ] & sum [ 3 ] ....& sum [ k ] 的最大值

分析

1.因为是按位运算要求最大值，首先应该想到的是按位贪心，即从高位到低位贪心。在保证了某一位能够为1时，再去考虑下一位
2. 设 表示把前j本书放入前i个书架中，能否使二进制的第x位为1，因为我们要固定之前的高位，所以这里的x得累计之前的高位有效的1

代码

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int N=110;

int n,k;
ll a[N],sum[N];
bool f[N][N];

inline bool check(ll mid)
{
    memset(f,0,sizeof(f));
    f[0][0]=1;
    for (int i=1;i<=k;i++)//前i个书架    
        for (int j=1;j<=n;j++)//前j本书 
            for (int p=0;p<j;p++)
                f[i][j]|=(f[i-1][p]&(((sum[j]-sum[p])&mid)==mid));

    return f[k][n];
}

int main()
{
    scanf("%d%d",&n,&k);
    for (int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        sum[i]=sum[i-1]+a[i];
    }

    ll ans=0;
    for (int i=60;i>=0;i--)
    {
        ll ok=(ans|(1ll<<i));
        if(check(ok)) ans=ok;
    }

    printf("%lld\n",ans);

    return 0;
}