[洛谷P3943]星空（BFS+状压DP）

题意

有\(n\)个灯泡，除了\(k\)个之外都是亮的，有\(m\)种长度的区间翻转，求最少次数使得所有所有灯泡都亮，保证有解，\((n\leq 40000,k\leq 8,m\leq 64)\)

思路

可以发现区间翻转之后区间内的相对关系不变；

第一步：将区间翻转转换成单点翻转？考虑差分，令\(pre_i\)表示\(i\)与\(i-1\)的异或值（注意第0位默认灯是打开的），于是区间翻转变成了单点翻转，即操作区间的左端点和右端点的右一位会翻转

第二步：预处理：可以发现一次翻转操作只会改变0或者2个1，所以1一定是成对消去的，对于每个1都bfs一遍即可得到将一对1消除的代价，这一步类似华容道的预处理操作

第三步：知道一对1消去的代价，直接状态压缩DP即可

当最后一位为0时为什么会只有奇数个1？（如样例），因为还需要算上第\(n+1\)位

时间复杂度\(O(nm+4^k*k)\)

Code

#include<bits/stdc++.h>
#define N 40005
#define Min(x,y) ((x)<(y)?(x):(y))
#define Max(x,y) ((x)>(y)?(x):(y))
using namespace std;
typedef long long ll;
int n,k,m,a[20],b[100];
int s[N],pre[N];//前缀异或和 
int one[N],tot;//所有1的位置 
int dis[20][N];
ll f[1<<17];
bool vis[N];

template <class T>
void read(T &x)
{
    char c; int sign=1;
    while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
    while((c=getchar())>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48; x*=sign;
}

void bfs(int s,int *dis)
{
    memset(vis,0,sizeof(vis));
    queue<int> q;
    while(!q.empty()) q.pop();
    dis[s]=0; vis[s]=1; q.push(s);
    while(!q.empty())
    {
        int u=q.front(); q.pop();
        for(int i=1;i<=m;++i)
        {
            int x=u-b[i];
            if(x>0&&!vis[x])
            {
                vis[x]=1;
                dis[x]=dis[u]+1;
                q.push(x);
            }
            x=u+b[i];
            if(x<=n+1&&!vis[x])
            {
                vis[x]=1;
                dis[x]=dis[u]+1;
                q.push(x);
            }
        }
    }
}
int getdis(int x,int y) { return dis[x][one[y]]; }//查询翻转(x,y)需要的代价 
int main()
{
    freopen("starlit.in","r",stdin);
    freopen("starlit.out","w",stdout);
    read(n);read(k);read(m);
    for(int i=0;i<N;++i) s[i]=1;
    for(int i=1;i<=k;++i) read(a[i]),s[a[i]]=0;
    for(int i=1;i<=n+1;++i) pre[i]=(s[i]^s[i-1]);
    for(int i=1;i<=m;++i) read(b[i]);
    memset(dis,50,sizeof(dis));
    for(int i=1;i<=n+1;++i)
    {
        if(pre[i])//从i(1)向其他点跑最短路 
        {
            one[++tot]=i;
            bfs(i,dis[tot]);
        }
    }
    memset(f,50,sizeof(f));
    f[0]=0;//状态为sta时的最小代价
    for(int i=0,t=(1<<tot)-1;i<t;++i)//刷表 
    {
        int fir=-1;//找到第一个0 
        for(int j=0;j<tot;++j) if(!(i>>j&1)) { fir = j; break; }
        for(int j=fir+1;j<tot;++j)//第二个0 
          if(!(i>>j&1))
          {
            int now=(i|(1<<fir))|(1<<j);
            f[now]=Min(f[now] , f[i] + getdis(fir+1,j+1));
          }
    }
    cout<<f[(1<<tot)-1]<<endl;
    return 0;
}