Bookshelves

定义为前个书分成组的最大价值

这么转移是有后效性的

价值不是越大越好

观察到价值计算是与运算,可以一位一位单独考虑

比如,如果每组都能凑齐,那这一位上必然是

然后考虑能否凑齐,但是同时也要凑齐...

就这样一位一位去判断

还是比较显然的....

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 59;
int f[maxn][maxn],a[maxn],k,n,pre[maxn];
bool ok(int x,int y){
    return ((x&y)==x);
}
bool isok(int x)
{
    memset( f,0,sizeof f);
    for(int i=1;i<=n;i++)    f[i][1] = ok(x,pre[i]);
    for(int i=2;i<=n;i++)
    {
        int limit = min( i,k );
        for(int j=2;j<=limit;j++)//分组情况 
        for(int q=1;q<i;q++)
            f[i][j] |= ( f[q][j-1]&ok(x,pre[i]-pre[q]) );
    }
    return f[n][k];
}
signed main()
{
    cin >> n >> k;
    for(int i=1;i<=n;i++)    cin >> a[i], pre[i] = pre[i-1]+a[i];
    //定义f[i][j]为前i本书分成j个书柜的最大价值...
    //这样肯定是有后效性的,因为不是越大越好
    int base = ((int)1<<61), ans = 0;
    //是否可能保持每组都有base呢? 
    for(int i=0;i<=61;i++)
    {
        if( isok( ans+base ) )    ans += base;
        base /= 2;
    }
    cout << ans;
}