「Codeforces 981D」Bookshelves

发表于 | | 阅读次数:
字数统计: 479 字

Description

题目链接：Codeforces 981D

给出 $n​$ 本书，每本书有一个价值 $a_i​$。将这 $n​$ 本书按照顺序放到 $k​$ 个书架上（连续若干本书放在一个书架上，接下来连续若干本放在下一个书架上），定义一个书架的美观程度为这个书架上所有书的价值总和，定义 $k​$ 个书架的美观程度为每个书架美观程度的按位与和，求这 $k​$ 个书架的最大美观程度。

数据范围：$1\le k\le n\le 50$，$0<a_i<2^{50}$

Solution

对于按位与和，我们可以从高位到低位贪心选择。这个贪心的证明显然：如果一位为 $1$ 肯定比这一位为 $0$ 且后面都为 $1$ 更优。

如果当前最优解为 $ans$，接下来贪心第 $i$ 位，我们用 $\text{DP}$ 验证 $ans’=ans\ \text{OR}\ 2^i$ 这个答案是否可行。$\text{DP}$ 的状态定义为：$f[i][j]$ 表示前 $i$ 本书放到 $j$ 个书架是否可以得到答案 $x$ 使得 $ans’\in x$（$x\ \text{AND}\ ans’=ans’$）。转移方程为 $f[i][j]|=f[k][j-1]\ \text{AND}\ [sum(k+1,i)\ \text{AND}\ x=x]$，如果 $f[n][k]=1$ 则直接更新答案。

时间复杂度：$O(n^2 k\log \sum a_i)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
#include <cstdio>
#include <cstring>

const int N=55;
int n,k;
long long a[N];
bool f[N][N];

bool check(long long x) {
    memset(f,0,sizeof(f));
    f[0][0]=1;
    for(int i=1;i<=n;++i) {
        for(int j=1;j<=k;++j) {
            for(int k=0;k<i;++k) {
                f[i][j]|=f[k][j-1]&(((a[i]-a[k])&x)==x);
            }
        }
    }
    return f[n][k];
}
int main() {
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i) scanf("%lld",&a[i]),a[i]+=a[i-1];
    long long ans=0;
    for(int i=60;i>=0;--i) {
        long long now=ans|(1LL<<i);
        if(check(now)) ans|=(1LL<<i);
    }
    printf("%lld\n",ans);
    return 0;
}
0%