题解 P3943 星空

· · 个人记录

Solution

设关闭的灯在原序列上表示为 1 , 先把原序列做一个异或差分 , 即 b_i=a_i\ xor\ a_{i-1} , 那么我们的区间操作就变成了对差分序列上一定距离的两个数取反 , 目标是把整个差分序列变为 0 .
显然我们每次操作至少对一个 1 取反 , 考虑两种情况

  1. 对一个 1 和 0 取反 , 可以看作把 1 移到 0 的位置
  2. 对两个 1 取反 , 可以看作把一个 1 移到另一个 1 的位置 , 然后消去两者

这样问题就变成了把若干个 1 一一配对 , 并把两者移动到相同位置的最小步数 , 由于 k\leq8 , 那么 1 的个数 \leq16 . bfs 出每个 1 移动到另一个 1 的最小步数 , 状压 dp 处理即可 .
复杂度 O(knm+2^{2k}k^2)

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int read()
{
    int ret=0;char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')ret=(ret<<3)+(ret<<1)+(c^48),c=getchar();
    return ret;
}
const int maxn=4e4+5;
const int maxm=65;
const int maxk=17;
const int inf=1e9;
int n,k,m;
bool a[maxn];int b[maxn];
int cnt,p[maxk],dis[maxk][maxk];
int step[maxn];
int f[1<<16];
queue<int>q;bool vis[maxn];
void bfs(int x)
{
    while(!q.empty())q.pop();
    q.push(x);
    memset(vis,0,sizeof(vis));
    while(!q.empty())
    {
        int now=q.front();q.pop();
        for(int i=1;i<=m;i++)
        {
            if(now-b[i]>0&&!vis[now-b[i]])vis[now-b[i]]=1,step[now-b[i]]=step[now]+1,q.push(now-b[i]);
            if(now+b[i]<=n&&!vis[now+b[i]])vis[now+b[i]]=1,step[now+b[i]]=step[now]+1,q.push(now+b[i]);
        }
    }
}
int main()
{
    n=read()+1;k=read();m=read();
    for(int i=1;i<=k;i++)a[read()]=1;
    for(int i=1;i<=m;i++)b[i]=read();
    for(int i=n;i>=1;i--)if(a[i]^a[i-1])p[++cnt]=i;
    for(int i=1;i<=cnt;i++)
    {
        step[p[i]]=0;
        bfs(p[i]);
        for(int j=1;j<=cnt;j++)dis[i][j]=vis[p[j]]?step[p[j]]:maxn;
    }
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=0;i<(1<<cnt);i++)
    {
        for(int j=1;j<=cnt;j++)
        {
            if(i&(1<<(j-1)))continue;
            for(int k=1;k<=cnt;k++)
            {
                if(j==k)continue;
                if(i&(1<<(k-1)))continue;
                f[i|(1<<(j-1))|(1<<(k-1))]=min(f[i^(1<<(j-1))^(1<<(k-1))],f[i]+dis[j][k]);
            }
        }
    }
    printf("%d",f[(1<<cnt)-1]);
    return 0;
}