题目描述
印尼巴厘岛的公路上有许多的雕塑,我们来关注它的一条主干道。
在这条主干道上一共有 NN 座雕塑，为方便起见，我们把这些雕塑从 11 到 NN 连续地进行标号，其中第 ii 座雕塑的年龄是 Y_iYi 年。为了使这条路的环境更加优美，政府想把这些雕塑分成若干组，并通过在组与组之间种上一些树，来吸引更多的游客来巴厘岛。
下面是将雕塑分组的规则：
这些雕塑必须被分为恰好 XX 组，其中 A \leq X \leq BA≤X≤B，每组必须含有至少一个雕塑，每个雕塑也必须属于且只属于一个组。同一组中的所有雕塑必须位于这条路的连续一段上。
当雕塑被分好组后，对于每个组，我们首先计算出该组所有雕塑的年龄和。
计算所有年龄和按位取或的结果。我们这个值把称为这一分组的最终优美度。
请问政府能得到的最小的最终优美度是多少?
输入输出格式
输入格式：
输入的第一行包含三个用空格分开的整数 N, A, BN,A,B。
第二行包含 N 个用空格分开的整数 Y_1, Y_2, ,,, Y_N
输出格式：
输出一行一个数，表示最小的最终优美度。
输入输出样例
6 1 3
8 1 2 1 5 4
11
说明
【样例解释】
将这些雕塑分为 22 组，(8, 1, 2)(8,1,2) 和 (1, 5, 4)(1,5,4)，它们的和是 (11)(11) 和 (10)(10)，最终优美度是 (11 \mathbin{\mathrm{OR}} 10) = 11(11OR10)=11。（不难验证，这也是最终优美度的最小值。）
有两种子任务：
part 1: n<=100,A,B<=n；
part 2: n<=2000,A=1,B<=n。
(神TM一直把取或看成异或，，，)
位运算的最优化问题很多都可以拆位贪心的，因为我们让高位尽量不为1了之后，答案肯定比这位是1要更优。
所以我们总体的思路就是从高位到低位每一位判断它是否可以为0，并且还要保证之前为0的更高位现在还是0。
因为是取或，所以如果答案的这一位是0的话，就意味着每一组的和的这一位都是0。
1.对于第一个子任务，设dp[i][j]为前i棵树分成j组可不可行(bool 数组就行了)。
2.对于第二个子任务，设dp[i]为前i棵树分成的最小组数(因为A=1,所以在合法的情况下肯定是组数越少越好)
转移不难，懒得写了。
（以后请在做题之前估算好数据范围23333）
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll ci[],n,A,B;
bool dp[][];
ll f[],s[];
ll alr,tp,all; inline void solve1(){
for(int i=tp;i>=;i--){
alr|=ci[i];
memset(dp,,sizeof(dp));
dp[][]=; for(int j=;j<n;j++)
for(int u=;u<=j;u++) if(dp[j][u]){
for(int k=j+;k<=n;k++) if(!((s[k]-s[j])&alr)) dp[k][u+]=;
} bool fl=;
for(int j=A;j<=B;j++) if(dp[n][j]){
fl=;
break;
}
if(!fl) alr^=ci[i];
}
} inline void solve2(){
for(int i=tp;i>=;i--){
alr|=ci[i];
memset(f,0x3f,sizeof(f));
f[]=; for(int j=;j<=n;j++)
for(int u=;u<j;u++) if(!((s[j]-s[u])&alr)) f[j]=min(f[j],f[u]+); if(f[n]>B) alr^=ci[i];
}
} int main(){
ci[]=;
for(int i=;i<=;i++) ci[i]=ci[i-]+ci[i-]; scanf("%lld%lld%lld",&n,&A,&B);
for(int i=;i<=n;i++){
scanf("%lld",s+i);
s[i]+=s[i-];
} for(int i=;i>=;i--) if(s[n]&ci[i]){
tp=i,all=ci[i+]-;
break;
} if(A>) solve1();
else solve2(); printf("%lld\n",all^alr);
return ;
}