定义集合 合法当且仅当满足以下条件:
;
, ;
给定 ,求最大的 。
,。
问题等价于找到一个长 的 01 序列满足序列中任意两个 的位置差不为 或 ,最大化 01 序列中 的个数。
引理 1
任意长 的合法的 01 序列无限重复构成的 01 序列仍然合法。
证明
反证法。
若存在一个长 的合法的 01 序列 满足其无限重复构成的 01 序列 中:
- 和 均为 :不妨假设 ,那么此时一定有 ,注意到 为 ,,所以此时 一定不合法;
- 和 均为 :同理,一定有 ;
Q.E.D.
定理 1
最优解一定是某个长 的合法 01 序列无限重复构成的 01 序列的长度为 的前缀。
证明
的情况下显然成立。
设 (),现在来证明最后一小段长 的跟着前面循环是不劣的:
- 反证法,设最后一小段长 的 01 序列为 ,设循环节(长度为 的不断出现的 01 串)为 ;
- 不跟着前面循环更优,当且仅当 (拼起来)合法但用 替换掉 的长 的前缀不合法,不妨设用 替换掉 的长 的前缀得到的字符串为 ;
- 设 中不合法的两个位置为 和 ( 同理),那么一定有 ;
- 考察答案的后缀 ,由于位置 和 都是 ,那么位置 和 一定也都是 ,那么 不合法,所以 不合法,矛盾;
Q.E.D.
那么 状压 dp 即可,代码如下:
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int BS=1<<22;
int n,x,y;
int f[2][BS];
int main()
{
scanf("%d%d%d",&n,&x,&y);
if(x<y) swap(x,y);
memset(f,128,sizeof(f));
int p=0;
f[p][0]=0;
for(int i=0;i<=x+y-1&&i<=n-1;i++)
{
p^=1;
memset(f[p],128,sizeof(f[p]));
for(int j=0;j<(1<<x);j++)
{
int s0=(j<<1)&((1<<x)-1),s1=s0|1;
if((s0&(j>>x-1))==0&&(s0&(j>>y-1))==0) f[p][s0]=max(f[p][s0],f[p^1][j]);
if((s1&(j>>x-1))==0&&(s1&(j>>y-1))==0) f[p][s1]=max(f[p][s1],f[p^1][j]+n/(x+y)+(i+1<=n%(x+y)));
}
}
int ans=0;
for(int i=0;i<(1<<x);i++) ans=max(ans,f[p][i]);
printf("%d\n",ans);
return 0;
}