Bookshelves

题意：
给你一个长度为n的数组，请你按顺序分成k份，然后将每一份的和进行位与操作，求结果最大为多少？

思路：
从高位到低位枚举结果，即如果加入该位后结果满足条件则将该位加入结果，否则舍弃该位。
判断结果是否满足条件使用dp：
dp[i][j]表示将前i个数分成j组是否满足条件；
dp[i][j]=(dp[i][j]||((dp[l][j-1])&&(((sum[i]-sum[l])&x)==x)));(x表示你要判断的结果，dp[l][j-1]表示前l个数是否能分成j-1组，((sum[i]-sum[l])&x)==x))表示[l+1,i]是否能分成1组，当二者都成立是dp[i][j]必定成立）；
判断结果为dp[n][k];

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll a[105], sum[105];

ll dp[105][105];
int n, k;

bool fun(ll x)
{
    //cout << x << endl;
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    for(int i=1;i<=k;i++)
    {
        for(int r=1;r<=n;r++)
        {
            for(int l=0;l<r;l++)
            {
                dp[r][i]=(dp[r][i]||((dp[l][i-1])&&(((sum[r]-sum[l])&x)==x)));
            }
        }
    }
    return  dp[n][k];
}

int main()
{
    scanf("%d%d",&n,&k);
    sum[0]=0;
    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 x=(ans|(1LL<<i));
        if(fun(x))
        {
            ans=x;
        }
    }
    cout << ans << endl;
    return 0;
}