[APIO2015]巴厘岛的雕塑

时间：2023-01-27 19:39:01

题目描述

印尼巴厘岛的公路上有许多的雕塑,我们来关注它的一条主干道。

在这条主干道上一共有 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

输出格式：

输出一行一个数，表示最小的最终优美度。

输入输出样例

输入样例#1： 
6 1 3

8 1 2 1 5 4
输出样例#1： 
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 ;

}

相关文章