【Bzoj4069】【Luogu3646】巴厘岛的雕塑

来源和评测点

Apio2015 Bali Sculptures
Bzoj4069
Luogu3646
Uoj110

题目

【题目大意】
给出一些有序的值,在连续的情况下进行分组,
并且a<=组的数量<=b
求最小的 所有(组的和)的按位或值。
【输入格式】
输入的第一行包含三个用空格分开的整数N,A,B
第二行包含N个用空格分开的整数。
【输出格式】
输出一行一个数,表示最小的按位或值。
【限定条件】
子任务1 (9 分)
1<=N<=20
1<=A<=B<=N
0<=Yi<=1000000000

子任务2 (16 分)
1<=N<=50
1<=A<=B<=min{20,N}
0<=Yi<=10

子任务3 (21 分)
1<=N<=100
A=1
1<=B<=N
0<=Yi<=20

子任务4 (25 分)
1<=N<=100
1<=A<=B<=N
0<=Yi<=1000000000

子任务5 (29 分)
1<=N<=2000
A=1
1<=B<=N
0<=Yi<=1000000000
【输入样例】
6 1 3
8 1 2 1 5 4
【输出样例】
11
【样例解释】
分为2组,(8,1,2)和(1,5,4),它们的和是 (11) 和 (10),
最终优美度是 (11 OR 10)=11,不难验证,这也是最终优美度的最小值。

刷题记录

1h

分析

请先思考后再展开

显然,直接写dp是不行的,因为区间小并不代表最终小。
既然是按位或,可以考虑数位dp。
然后区间静态求和,前缀和是不能少滴。

然后网上看到一句话:

对于数位极值问题,应该贪心地优先从高位开始考虑,
极小值优先0,极大值优先1

然后就可以愉快地考虑dp了:
假设现在在努力地把右数第k位变成0,
那么我们就要尽量让所有和的第k位为0。
并且前面的已经解决,用tmp表示现在已经能变成0的位置
(所以最后输出答案就是tot-tmp)

然后f[i][p]表示前面i个数分p段能否第k位是0(状压),然后n^2来常规dp即可
转移条件:( (sum[i]-sum[j])&tmp )==0 (也就是tmp为1的地方这一段的和必须是0,否则前功尽弃)
那么这个复杂度是O(60*n^3)的,而最后一个子任务是2000,会TLE
然后发现这一次,A=1,那么怎么利用这个条件呢?
考虑贪心一波:因为现在的限制只有B,那么当然是段数越小,成功率越高。
设g[i]表示前i个数最小分多少段能第k位是0
成功变成O(60*n^2)

代码

请先思考后再展开
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
//Zory in 2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<string>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
//*******************全局常量*******************
const int MAXN=2100;
//*******************全局定义*******************
typedef long long ll;
int n,A,B;
ll sum[MAXN];
ll bin[70];
//*******************实现*******************
bool f[MAXN][MAXN];
ll dp1(ll kk)
{
ll tmp=0;
for(int k=kk-1;k>=0;k--)
{
tmp+=bin[k];//先假设成功
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++) f[i][1]=( (sum[i]&tmp)==0 );
bool bk=(A==1 and f[n][1]);
for(int p=2;p<=B;p++)
{
if(bk) break;
for(int i=p;i<=n;i++)
{
for(int j=p-1;j<=i-1;j++)
if(f[j][p-1] and ((sum[i]-sum[j])&tmp)==0)
{ f[i][p]=1;break; }
if(p>=A and f[n][p]) {bk=1;break;}
}
}
if(!bk) tmp-=bin[k];
}
return (bin[kk]-1)-tmp;
}
int g[MAXN];
ll mymin(ll x,ll y) {return x<y?x:y;}
ll dp2(ll kk)
{
ll tmp=0;
for(int k=kk-1;k>=0;k--)
{
tmp+=bin[k];//先假设成功
memset(g,63,sizeof(g));g[0]=0;
for(int i=1;i<=n;i++)
for(int j=0;j<=i-1;j++)
if( ((sum[i]-sum[j])&tmp)==0 )
g[i]=mymin(g[i],g[j]+1);
if(g[n]>B) tmp-=bin[k];
}
return (bin[kk]-1)-tmp;
}
//*******************主函数*******************
int main()
{
scanf("%d%d%d",&n,&A,&B);
for(int i=1;i<=n;i++)
{
int t;scanf("%d",&t);
sum[i]=sum[i-1]+t;
}
int kk;
for(kk=0;kk<=60;kk++)
{
bin[kk]=(kk==0)?1:(bin[kk-1]<<1);
if(bin[kk]-1>=sum[n]) return printf("%lld",(A>1)?dp1(kk):dp2(kk)),0;
}
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/a4aa.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%