luogu3646&&bzoj4069 [APIO2015]巴厘岛的雕塑

luogu3646&&bzoj4069 [APIO2015]巴厘岛的雕塑

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

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

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

这些雕塑必须被分为恰好 XX 组，其中 A≤X≤BA≤X≤B ，每组必须含有至少一个雕塑，每个雕塑也必须属于且只属于一个组。同一组中的所有雕塑必须位于这条路的连续一段上。 当雕塑被分好组后，对于每个组，我们首先计算出该组所有雕塑的年龄和。 计算所有年龄和按位取或的结果。我们这个值把称为这一分组的最终优美度。 请问政府能得到的最小的最终优美度是多少?

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

首先把 PP 和 QQ 转换成二进制。 设 nPnP 是 PP 的二进制位数，nQnQ 是 QQ 的二进制位数，MM 为 nPnP 和 nQnQ 中的最大值。PP 的二进制表示为 pM−1pM−2…p1p0pM−1pM−2…p1p0 ，QQ 的二进制表示为 qM−1qM−2…q1q0qM−1qM−2…q1q0 ，其中 pipi 和 qiqi 分别是 PP 和 QQ 二进制表示下的第 ii 位，第 M−1M−1 位是数的最高位，第 00 位是数的最低位。 PP 与 QQ 按位取或后的结果是： (pM−1ORqM−1)(pM−2ORqM−2)…(p1ORq1)(p0ORq0)(pM−1ORqM−1)(pM−2ORqM−2)…(p1ORq1)(p0ORq0) 。其中： 0OR0=00OR0=0 0OR1=10OR1=1 1OR0=11OR0=1 1OR1=11OR1=1 输入格式 输入的第一行包含三个用空格分开的整数 N,A,BN,A,B 。

第二行包含 NN 个用空格分开的整数 Y1,Y2,…,YNY1,Y2,…,YN 。

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

样例一 input

6 1 3 8 1 2 1 5 4

output

11

explanation

将这些雕塑分为 22 组，(8,1,2)(8,1,2) 和 (1,5,4)(1,5,4) ，它们的和是 (11)(11) 和 (10)(10) ，最终优美度是 (11OR10)=11(11OR10)=11 。（不难验证，这也是最终优美度的最小值。）

子任务 子任务 1 （9 分） 1≤N≤201≤N≤20 1≤A≤B≤N1≤A≤B≤N 0≤Yi≤10000000000≤Yi≤1000000000 子任务 2 （16 分） 1≤N≤501≤N≤50 1≤A≤B≤min{20,N}1≤A≤B≤min{20,N} 0≤Yi≤100≤Yi≤10 子任务 3 （21 分） 1≤N≤1001≤N≤100 A=1A=1 1≤B≤N1≤B≤N 0≤Yi≤200≤Yi≤20 子任务 4 （25 分） 1≤N≤1001≤N≤100 1≤A≤B≤N1≤A≤B≤N 0≤Yi≤10000000000≤Yi≤1000000000 子任务 5 （29 分） 1≤N≤20001≤N≤2000 A=1A=1 1≤B≤N1≤B≤N 0≤Yi≤10000000000≤Yi≤1000000000 时间限制：1s1s

空间限制：64MB

第一次写数位dp

一开始第一眼想到dp 但是没想到数位dp 如果朴素的写dp 方程那么我不能保证每次or的最小就能使后面的or小

于是在leoly的介绍下，学习了数位dp

一共这些数加起来是2000*10^9

我们对于他的每一个二进制位去dp 然后贪心的从最高位开始做

那么前5个子任务 中的四个是100以内的

我们定义方程f[i][j]表示前1~i个间分j组 能否满足条件

这个满足条件的含义很多就是我现在这个数位能否是0

f[i][j]表示1~i分成j个，当前数位可以是0 tmp用来储存我此前已经确定了的最优值，每回做的时候我先认为这个地方可以是0 那么tmp这一位就需要+1 然后每次用位运算去判断能否满足条件

时间复杂度:100^3*log2(和最大)

那么这种复杂度显然子任务5是做不了的，观察到子任务5 A的范围就是1说明我们只要看满足条件（最优分法）的组数是否超过了B

样例的二进制

01000

00001

00010

00001

00101

00100 每次都是一个数位从上往下 注意小细节：如1LL<< 以及可能存在全是0的情况

#include #include#include#include#define inf 0x7f7f7f7fusing namespace std;#define N 2200inline int read(){ int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();} while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x*f;}int A,B,n,a[N];long long sum,s[N];bool f[N][N];int g[N];void dp1(){ int kk=log2(sum);long long tmp=0; for (int p=1;p<=kk+1;++p){ memset(f,0,sizeof(f));tmp+=1LL<=A&&j<=B) if (!flag&&f[n][j]) flag=true; } if (f[n][1]) flag=true; if (!flag) tmp-=1LL<B) tmp-=1LL<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。