洛谷P3943 星空

看题解系列

首先是异或差分（其实我也不知道叫什么）
定义f 为异或数组

$$f\left [ i \right ]=w\left [ i \right ]\ xor \ w\left [ i+1 \right ]$$

表示$w\left [ i \right ]\$ 与$\ w\left [ i+1 \right ]$ 是否相同
f 数组中至多有 $2k$ 个 1 ，且肯定是偶数个
当f 数组全部为0 时，灯全部点亮
对于一段连续序列进行翻转，显然只需要修改$f\left [ l-1 \right ]$，$f\left [ r \right ]$
这个操作等价于对某个元素进行移动
当两个1 相遇时会消除
于是问题等价于求所有1 消除的代价
对于任意两个1 消除的代价，可用完全背包求
将长度为len 的操作看成len 和-len 两种
最后状压所有1

$$dp\left [ s' \right ]=min\left \{ dp\left [ s \right ] +cost\left [ i,j \right ]\right \}\left ( i\notin s,j\notin s \right )$$

乍一看枚举i ，j 复杂度$O\left ( 2^{N}N^{2} \right )$
但实际上其中一个并不用枚举，确定任意一个i 之后枚举j 即可
因此复杂度$O\left ( 2^{N}N \right )$

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=18,M=40050,INF=1<<25;
int n,k,m,dp[1<<N],d[M],idx[1<<N];
int pos[M],cnt=0,w[M],f[M],v[M];
inline int read()
{
    register int x=0,t=1;
    register char ch=getchar();
    while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if (ch=='-') t=-1,ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
    return x*t;
}
int main()
{
    n=read()+1,k=read(),m=read();
    for(int i=1;i<=k;i++) w[read()]=1;
    for(int i=1;i<=m;i++) v[i]=read();
    for(int i=0;i<n;i++) f[i]=w[i]^w[i+1];
    for(int i=0;i<n;i++) 
        if (f[i]) pos[++cnt]=i;
    for(int i=1;i<=n;i++) d[i]=INF;
    for(int i=1;i<=m;i++)
        for(int j=v[i];j<=n;j++)
            d[j]=min(d[j],d[j-v[i]]+1);
    for(int i=1;i<=m;i++)
        for(int j=n-v[i];j>=0;j--)
            d[j]=min(d[j],d[j+v[i]]+1);
    for(int s=1;s<(1<<cnt);s++) dp[s]=INF;
    for(int s=0;s<(1<<cnt);s++)
        for(int i=1;i<=cnt;i++) idx[s]+=(s>>(i-1))&1;
    for(int x=1,s=0;s<(1<<cnt);s++,x=1) if (idx[s]&1^1)
    {
        while ((s>>(x-1))&1) x++;
        for(int i=x+1;i<=cnt;i++) if ((s>>(i-1))^1)
            if (i!=x&&d[pos[i]-pos[x]]!=INF)
                dp[s|(1<<(i-1))|(1<<(x-1))]=min(dp[s|(1<<(i-1))|(1<<(x-1))],dp[s]+d[pos[i]-pos[x]]);
    }
    printf("%d\n",dp[(1<<cnt)-1]);
    return 0;
}