【APIO2015】Bali Sculptures

题目描述

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

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

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

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

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

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

首先把 $P$ 和 $Q$ 转换成二进制。
设 $n_P$ 是 $P$ 的二进制位数，$n_Q$ 是 $Q$ 的二进制位数，$M$ 为 $n_P$ 和 $n_Q$ 中的最大值。$P$ 的二进制表示为 $p_{M−1} p_{M−2} \dots p_1 p_0$，$Q$ 的二进制表示为 $q_{M−1} q_{M−2} \dots q_1 q_0$，其中 $p_i$ 和 $q_i$ 分别是 $P$ 和 $Q$ 二进制表示下的第 $i$ 位，第 $M − 1$ 位是数的最高位，第 $0$ 位是数的最低位。
$P$ 与 $Q$ 按位取或后的结果是： $(p_{M−1} \mathbin{\mathrm{OR}} q_{M−1})(p_{M−2} \mathbin{\mathrm{OR}} q_{M−2}) \dots (p_1 \mathbin{\mathrm{OR}} q_1) (p_0 \mathbin{\mathrm{OR}} q_0)$。其中：
- $0 \mathbin{\mathrm{OR}} 0 = 0$
- $0 \mathbin{\mathrm{OR}} 1 = 1$
- $1 \mathbin{\mathrm{OR}} 0 = 1$
- $1 \mathbin{\mathrm{OR}} 1 = 1$

输入格式

输入的第一行包含三个用空格分开的整数 $N, A, B$。

第二行包含 $N$ 个用空格分开的整数 $Y_1, Y_2, \dots, Y_N$。

输出格式

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

这道dp好大啊...........

我们分五个子任务分别来讨论一下

子任务

子任务 1 （9 分）
- $1 \leq N \leq 20$
- $1 \leq A \leq B \leq N$
- $0 \leq Y_i \leq 1000000000$

分析

暴枚分割点，有$n-1$个分割点，$O(2^{n-1}*n)$即可解决

子任务 2 （16 分）
- $1 \leq N \leq 50$
- $1 \leq A \leq B \leq \min\{20, N\}$
- $0 \leq Y_i \leq 10$

分析

观察到这个任务的特点，$Y_i$很小，我们可以考虑用dp的状态来记录$Y_i$

$f[i][j][k]$表示前$i$个数，分成$j$组，和的或为$k$是否可行

$O(n)$枚举每一个位置，对于每一个位置，$O(n^2)$枚举当前区间的开始位置和前面有几个区间，暴力转移

时间复杂度$O(n^3*y)$

子任务 3 （21 分）
- $1 ≤ N ≤ 100$
- $A = 1$
- $1 \leq B \leq N$
- $0 \leq Y_i \leq 20$

分析

观察到这个任务的特点，$Y_i$也比较小，而且$A=1$，显然刚才的状态数量过多，需要减少

$f[i][j]$表示前$i$个数，和的或为$j$的最少分组，因为分组下届为$1$，那么，我们只要尽可能的减少分区，与$B$相比较，既可以得到最小的和的或了

$O(n)$枚举每一个位置，对于每一个位置，$O(n)$枚举当前区间的开始位置，暴力转移

时间复杂度$O(n^2*y)$

子任务 4 （25 分）
- $1 \leq N \leq 100$
- $1 \leq A \leq B \leq N$
- $0 \leq Y_i \leq 1000000000$

分析

可以发现，这其实是子任务2的升级版

而这时，和的或状态显然已经记不下来了，这个时候我们考虑贪心

我们按位来确定，显然，对于每一个要确定的位，只要他能$0$，就不可能让他$1$

那么，我们贪心的确定最高位，根据最高位一次确定次高位......

然后对于每一位，考虑用dp来验证

假设当前为$0$,$f[i][j]$表示前$i$个数，分成$j$组，是否可行

可行则为$0$，否则当前为只能为$1$，一次贪心地确定下去

时间复杂度$O(n^3*logy)$

子任务 5 （29 分）
- $1 \leq N \leq 2000$
- $A = 1$
- $1 \leq B \leq N$
- $0 \leq Y_i \leq 1000000000$

分析

和子任务4类似的，可以发现他是子任务3的升级版本

那么，同样按位贪心地确定

假设当前为$0$，$f[i]$表示前$i$个数，最少分组，当$f[n]\leq B$的时候，满足要求，当前为就设为$0$了，否则为$1$，依次确定下去

时间复杂度$O(n^2*logy)$

<br >

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstdlib>

#include<cstring>

#include<string>

#include<climits>

#include<vector>

#include<cmath>

#include<map>

#define LL long long

#define pii pair<int,int>

#define mp make_pair

using namespace std;

inline char nc(){

  static char buf[100000],*p1=buf,*p2=buf;

  if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }

  return *p1++;

}

inline void read(int &x){

  char c=nc();int b=1;

  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;

  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;

}

inline void read(LL &x){

  char c=nc();LL b=1;

  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;

  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;

}

inline int read(char *s)

{

	char c=nc();int len=1;

	for(;!(c>='a' && c<='z');c=nc()) if (c==EOF) return 0;

	for(;(c>='a' && c<='z');s[len++]=c,c=nc());

	s[len++]='\0';

	return len;

}

inline void read(char &x){

  for (x=nc();!(x>='A' && x<='Z');x=nc());

}

int wt,ss[19];

inline void print(int x){

	if (x<0) x=-x,putchar('-');

	if (!x) putchar(48); else {

	for (wt=0;x;ss[++wt]=x%10,x/=10);

	for (;wt;putchar(ss[wt]+48),wt--);}

}

inline void print(LL x){

	if (x<0) x=-x,putchar('-');

	if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}

}

int n,A,B,b[50],f1[51][51][600],f3[110][110],f4[2010],ans[50];

LL Min,a[2010],f2[110][3000];

bool check()

{

	int s=1;

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

		s+=b[i];

	return (s>=A) && (s<=B);

}

void pp(int x)

{

	if (x==n)

	{

		if (check())

		{

			LL s=0,t=0;b[n]=1;

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

			{

				t=t+a[i];

				if (b[i]==1) s|=t,t=0;

			}

			Min=min(Min,s);

		}

		return ;

	}

	for (int i=0;i<=1;i++)

		b[x]=i,pp(x+1);

}

int check(LL x,int z)

{

	int y[50],s=0,j;

	memset(y,0,sizeof(y));

	while (x) y[++s]=x%2,x/=2;

	for (int i=41;i>=z;i--)

		if (!ans[i] && y[i]) return 0;

	for (int i=41;i>=z;i--)

		if (ans[i]!=y[i]) return 1;

	return 2;

}

bool check1(int x)

{

	memset(f3,0,sizeof(f3));

	f3[0][0]=2;

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

	{

		LL s=a[i];

		for (int j=i-1;j>=0;j--)

		{

			int t=check(s,x);

			if (t==1)

			{

				for (int k=0;k<=j;k++)

					if (f3[j][k]) f3[i][k+1]=f3[j][k];

			}

			else if (t==2)

			{

				for (int k=0;k<=j;k++)

					if (f3[j][k]) f3[i][k+1]=2;

			}

			s+=a[j];

		}

	}

	for (int i=A;i<=B;i++)

		if (f3[n][i]==2) return true;

	return false;

}

int check2(int x,LL y)

{

	memset(f4,0,sizeof(f4));

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

		f4[i]=n+1;

	f4[0]=0;

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

	{

		LL s=a[i];

		for (int j=i-1;j>=0;j--)

		{

			if (!(s&y))

				f4[i]=min(f4[i],f4[j]+1);

			s+=a[j];

		}

	}

	return f4[n];

}

int main()

{

	read(n);read(A);read(B);

	LL Max=0;

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

		read(a[i]),Max=max(Max,a[i]);

	if (n<=20)

	{

		Min=(1LL<<60)-1;

		pp(1);

		print(Min),puts("");

	}

	else if (n<=50 && Max<=10)

	{

		memset(f1,0,sizeof(f1));

		f1[0][0][0]=1;

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

		{

			int s=a[i];

			for (int j=i-1;j>=0;j--)

			{

				for (int k=0;k<=j;k++)

					for (int p=0;p<=511;p++)

						if (f1[j][k][p]) f1[i][k+1][p|s]=1;

				s+=a[j];

			}

		}

		Min=(1LL<<60)-1;

		for (int i=A;i<=B;i++)

			for (int j=0;j<=511;j++)

				if (f1[n][i][j]) Min=min(Min,(LL)j);

		print(Min),puts("");

	}

	else if (n<=100 && A==1 && Max<=20)

	{

		memset(f2,0,sizeof(f2));

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

			for (int j=0;j<=2047;j++)

				f2[i][j]=n+1;

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

		{

			int s=a[i];

			for (int j=i-1;j>=0;j--)

			{

				for (int k=0;k<=2047;k++)

					f2[i][k|s]=min(f2[i][k|s],f2[j][k]+1);

				s+=a[j];

			}

		}

		for (int i=0;i<=2047;i++)

			if (f2[n][i]<=B) {print(i),puts("");return 0;}

	}

	else if (n<=100)

	{

		memset(ans,0,sizeof(ans));

		for (int i=41;i>=1;i--)

			if (check1(i)) ans[i]=0;else ans[i]=1;

		Min=0;

		for (int i=41;i>=1;i--)

			Min=(Min<<1)+(LL)ans[i];

		print(Min),puts("");

	}

	else

	{

		memset(ans,0,sizeof(ans));LL p=0;

		for (int i=41;i>=1;i--)

			if (check2(i,p|(1LL<<(i-1)))<=B) ans[i]=0,p|=1LL<<(i-1);else ans[i]=1;

		Min=0;

		for (int i=41;i>=1;i--)

			Min=(Min<<1)+(LL)ans[i];

		print(Min),puts("");

	}

	return 0;

}

巴特西

【APIO2015】Bali Sculptures

题目描述

输入格式

输出格式

子任务

分析

分析

分析

分析

分析

最新文章

热门文章