这道题是2017.11.02 luogu模拟赛的T3
当时大家都只得了$8-12$分不等
------------
部分分做法：
- $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$
------------
发现$k$很小，考虑以$k$作为状态
因为涉及区间修改，可以将其转化到修改端点$→$差分
做异或差分，$b[i]=a[i] xor a[i+1]$
如果在$a$数组上反转$[l,r]$，相当于在$b$数组上对$b[l-1]$和$b[r]$取反
------------
问题转化为：一个长度为$n$的$01$串，其中有不超过$2k$个$0$，每次从$m$个长度中选择一个$len$，将相距为$len$的两点取反，问最少操作几次使得全部变为$1$
举个栗子：
$011101$
$110101$
$111111$
可以发现，如果一个位置是$0$，那么一定要进行操作来消去这个$0$
如果选择一个$1$和一个$0$，可以看作把$1$移动过来
如果选择两个$0$，可以看作把一个$0$移到另一个的位置并同时消去
------------
那么问题进一步转化：
一个长度为$n$的序列，有不超过$2k$个位置有物品，每次可以从$m$个距离中选择一个进行移动，两个物品放在一起会同时消去，最少操作几次可以消去所有物品
这样来看，最多有$2k$个起点，每个点有$m$条边，可以用$O(nmk)$的$bfs$预处理出两两之间的最短距离
------------
问题再次转化：
有$2k$个物品，两两可以消去，分别有不同的代价，求全部消去的最小代价
因为$k<=8$，所以状压$dp$即可
总复杂度$O(nmk+k2^{2k})$
```
#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;
}
```