P3943 星空

2018-09-17 20:27:21

• $4pts$ : $n=m=2,k<=2$ ,直接 $printf("\%d",1-(k==0))$

• $24pts$ : $n,m<=16$ ,直接对原序列状压 $dp$

复杂度 $O(m2^n)$

• $m=1$ ，从前往后贪心消去第一个 $1$

• 答案小于 $4$ ，特判答案为 $0$ 或 $1$ 的情况

爆搜得到答案为 $2$ 的情况，没有就输出 $3$

$011101$

$110101$

$111111$

#include<cstdio>
#include<cstring>
#include<cctype>
#include<queue>
#include<algorithm>
#define reg register
using namespace std;
const int N=4e4+5;
int n,k,m,a[N],len[65],pos[N],cnt;
int dis[N],d[17][17],r[1<<16],f[1<<16];
bool vis[N];
inline void Chkmin(int &a,int b){if (a>b) a=b;}
inline int read()
{
int x=0,w=1;
char c=getchar();
while (!isdigit(c)&&c!='-') c=getchar();
if (c=='-') c=getchar(),w=-1;
while (isdigit(c))
{
x=(x<<1)+(x<<3)+c-'0';
c=getchar();
}
return x*w;
}
inline void bfs(int s)
{
queue<int>q;
memset(dis,0,sizeof(dis));
memset(vis,0,sizeof(vis));
q.push(s); vis[s]=1;
while (!q.empty())
{
int u=q.front(); q.pop();
for (reg int i=1;i<=m;i++)
{
int x=u+len[i],y=u-len[i];
if (x<=n&&!vis[x]) dis[x]=dis[u]+1,q.push(x),vis[x]=1;
if (y>=0&&!vis[y]) dis[y]=dis[u]+1,q.push(y),vis[y]=1;
}
}
}
int main()
{
n=read(),k=read(),m=read();
for (reg int i=1;i<=k;i++) a[read()]=1;
for (reg int i=1;i<=m;len[i++]=read());
for (reg int i=0;i<=n;i++)
if (a[i]^a[i+1]) pos[++cnt]=i;
for (reg int i=1;i<=cnt;i++)
{
bfs(pos[i]);
for (reg int j=1;j<=cnt;j++) d[i][j]=dis[pos[j]];
}
for (reg int i=0;i<(1<<cnt);i++)
{
r[i]=cnt;
for (reg int k=1;k<=cnt;k++)
if (!((i>>k-1)&1)) {r[i]=k; break;}
}
memset(f,127/3,sizeof(f)); f[0]=0;
for (reg int i=0;i<(1<<cnt);i++)
for (reg int j=r[i]+1;j<=cnt;j++)
if ((!((i>>j-1)&1))&&d[r[i]][j])
Chkmin(f[i|(1<<r[i]-1)|(1<<j-1)],f[i]+d[r[i]][j]);
printf("%d\n",f[(1<<cnt)-1]);
return 0;
}
• star
首页