这题很劲啊
首先令b[i]=a[i]^a[i+1];
这样对a进行的区间操作即为对b的单点修改
目的变成了将b进行一些长度两端点的反转，使其全为0
考虑一个1，一个0，可以看做1移动到了0的位置，两个1呢，则可以看成撞到一起消去了
那么可以bfs处理出每两个1间的最短路，状压dp转移就好了
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<cmath> 6 #define N 40050 7 using namespace std; 8 int n,K,m; 9 int a[N],b[N],c[N],f[20][20],g[1<<20]; 10 int pos[20],tot; 11 int bit[20]; 12 int vis[N],dis[N]; 13 int q[N],head,tail; 14 int main(){ 15 bit[0]=1; 16 for(int i=1;i<=18;i++)bit[i]=bit[i-1]<<1; 17 scanf("%d%d%d",&n,&K,&m); 18 for(int i=1,x;i<=K;i++)scanf("%d",&x),a[x]=1; 19 for(int i=0;i<=n;i++)b[i]=a[i]^a[i+1]; 20 for(int i=1;i<=m;i++)scanf("%d",&c[i]); 21 for(int i=0;i<=n;i++)if(b[i])pos[++tot]=i; 22 for(int i=1;i<=tot;i++){ 23 memset(vis,0,sizeof vis); 24 memset(dis,0x3f,sizeof dis); 25 head=tail=1;q[1]=pos[i];vis[pos[i]]=1;dis[pos[i]]=0; 26 while(head<=tail){ 27 int x=q[head++]; 28 for(int i=1;i<=m;i++){ 29 if(x-c[i]>=0&&!vis[x-c[i]]){vis[x-c[i]]=1;dis[x-c[i]]=dis[x]+1;q[++tail]=x-c[i];} 30 if(x+c[i]<=n&&!vis[x+c[i]]){vis[x+c[i]]=1;dis[x+c[i]]=dis[x]+1;q[++tail]=x+c[i];} 31 } 32 } 33 for(int j=1;j<=tot;j++)f[i][j]=dis[pos[j]]; 34 } 35 memset(g,0x3f,sizeof g); 36 g[0]=0; 37 for(int i=0;i<bit[tot];i++){ 38 for(int j=1;j<=tot;j++)if(!(i&bit[j-1])) 39 for(int k=1;k<=tot;k++)if(k!=j&&(!(i&bit[k-1]))) 40 g[i|bit[j-1]|bit[k-1]]=min(g[i|bit[j-1]|bit[k-1]],g[i]+f[j][k]); 41 } 42 printf("%d ",g[bit[tot]-1]); 43 return 0; 44 }