巴厘岛的雕塑（sculptures）

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

在这条主干道上一共有 N 座雕塑，为方便起见，我们把这些雕塑从 1 到 N 连续地进行标号，其中第 i 座雕塑的年龄是 Yi 年。为了使这条路的环境更加优美，政府想把这些雕塑分成若干组，并通过在组与组之间种上一些树，来吸引更多的游客来巴厘岛。

下面是将雕塑分组的规则：

(1) 这些雕塑必须被分为恰好 X 组，其中 A≤X≤B，每组必须含有至少一个雕塑，每个雕塑也必须属于且只属于一个组。同一组中的所有雕塑必须位于这条路的连续一段上。

(2)当雕塑被分好组后，对于每个组，我们首先计算出该组所有雕塑的年龄和。

(3)计算所有年龄和按位取或的结果。我们这个值把称为这一分组的最终优美度。

请问政府能得到的最小的最终优美度是多少?

备注：将两个非负数 P 和 Q 按位取或是这样进行计算的：

(1) 首先把 P 和 Q 转换成二进制：设 nP是P的二进制位数，nQ是Q的二进制位数，M为 nP和nQ中的最大值。P的二进制表示为 pM-1 p M-2 ... p1 p0，Q 的二进制表示为 qM-1 qM-2 ... q1 q0，其中 pi 和 qi分别是 P 和 Q 二进制表示下的第 i 位，第 M−1 位是数的最高位，第 0 位是数的最低位。

(2) P 与 Q 按位取或后的结果是：

(pM-1 OR qM-1 )( p M-2 OR qM-2)...(p1 OR q1)( p0 OR q0)。其中：

0 OR 0 = 0 0 OR 1 = 1

1 OR 0 = 1 1 OR 1 = 1

|Subtask #|分值|$N$|$A,B$|$Y_i$|
|-|-|-|-|-|
|1|9|$N\le 20$|$1\le A\le B\le N$|$Y_i\le 10^9$|
|2|16|$N\le 50$|$1\le A\le B\le \min(20,N)$|$Y_i\le 10$|
|3|21|$N\le 100$|$A=1, 1\le B\le N$|$Y_i\le 20$|
|4|25|$N\le 100$|$1\le A\le B\le N$|$Y_i\le 10^9$|
|5|29|$N\le 2000$|$A=1, 1\le B\le N$|$Y_i\le 10^9$|

Solution

这数据范围是2合1啊

考虑 $N\le 100$ $1\le A\le B\le N$

设计dp f[i][j]表示前i个雕塑，分成j组的最大或。

然而这么dp会有后效性--前面最优不保证整体最优。

考虑在外面按位确定答案，转化为可行性问题，然后就可以dp了

效率O(n^3*60)

考虑 $N\le 2000$ $A=1, 1\le B\le N$

同样是按位确定答案，只是这时可简化状态为f[i]表示划分完前i个的最小段数。

效率O(n^2*60)

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cmath>

#define ll long long

using namespace std;

int n,f[][],A,B,g[];

ll a[],la;

int main(){

    cin>>n>>A>>B;

    for(int i=;i<=n;i++)scanf("%lld",&a[i]),a[i]+=a[i-];

    if(n<=){

        for(ll ws=;ws>=;ws--){

            la=la+(1LL<<ws);

            memset(f,,sizeof f);

            for(int i=;i<=;i++)f[][i]=;

            for(int i=;i<=n;i++){

                for(int j=;j<=i;j++){

                    for(int k=j-;k<i;k++){

                        f[i][j]|=(f[k][j-]&(((a[i]-a[k])&la)==));

                        if(ws==){

                            //printf("ws=%d  k=%d f[%d] [%d] =%d\n",ws,k,i,j,f[i][j]);

                            //printf("%d %d\n",(a[i]-a[k]),la,(a[i]-a[k])&la);

                        }

                    }

                }

            }

            int fl=;

            for(int i=A;i<=B;i++)if(f[n][i]){fl=;break;}

            if(!fl)la-=(1LL<<ws);

        }

    }

    else {

        for(ll ws=;ws>=;ws--){

            la=la+(1LL<<ws);

            memset(f,,sizeof f);

            for(int i=;i<=n;i++)g[i]=1e9;

            for(int i=;i<=n;i++){

                for(int j=;j<=i;j++){

                    if(((a[i]-a[j])&la)==)g[i]=min(g[i],g[j]+);

                }

            }

            if(g[n]>B)la-=(1LL<<ws);

        }

    }

    ll Max=(1LL<<)-;

    cout<<Max-la<<endl;

    return ;

}

巴特西

巴厘岛的雕塑（sculptures）

巴厘岛的雕塑（sculptures）

最新文章

热门文章