观察题目数据，发现 k ≤ 8 ，可能可以从这里入手解决问题
考虑状态压缩
但是我们每次操作都会让一连串的序列改变，而序列的每个状态都是必须要知道的
很麻烦，所以考虑如何把一段区间表示地简单一些
差分，把原序列转化成差分序列，原序列亮为0，暗为1，差分时用上一个数异或下一个数
那么原数列中一整段的数翻转在差分序列中就变成了几个数的变化
比如我们把第 l 到 r 的数翻转在差分序列中就是把第 l 个数翻转，第 r+1 个数翻转
在差分序列中的任意状态下都是这样
然后考虑结束状态，显然结束状态在差分序列中所有 1 都被翻转成 0
然后考虑翻转一段区间后差分序列状态的变化，显然翻转的两点至少一个点要包含1
不然只会让 1 越来越多，显然不会更优
考虑一个点为 1 的情况，1 变 0，另一个点的 0 变 1
其实就相当于 1 和 0 交换位置，相当于 1 走了长度为区间长度的路程（r-l+1） l + (r-l+1) = r+1
如果翻转区间的两点都为 1，那么翻转后它们都变为 0
其实相当于一个 1 走到另一个 1 的位置，然后它们互相抵消了
因为初始 1 的数量最多为 2k 个，而且只会越来越少，所以可以考虑状压DP
用BFS预处理出每一个 1 和其他的 1 抵消的最少步数
然后就直接DP转移就好了，转移和 noip2016 愤怒的小鸟 基本一样
设 p [ i ] [ j ] 表示第 i 个 1 和第 j 个 1 抵消的最少步数，那么
f [ i|(1<<j)|(1<<k) ] = min ( f [ i|(1<<j)|(1<<k) ]，f [ i ] + p [ j ] [ k ] )
并且因为从左往右第一个 1 迟早要被消去，所以 j 就固定为状态 i 从左往右第一个 1，然后只要枚举 k 就好了
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<queue> using namespace std; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=27,M=4e5+7; int n,m,K; int b[107]; int pos[N],tot; int dis[N][M],p[N][N]; bool vis[M]; queue <int> q; void pre_BFS()//BFS预处理每个1到所有其他1位置的最少步数 { int x,t; memset(dis,63,sizeof(dis)); memset(p,63,sizeof(p)); for(int i=1;i<=tot;i++)//枚举每个1 { memset(vis,0,sizeof(vis)); q.push(pos[i]); vis[pos[i]]=1; dis[i][pos[i]]=0;//初始状态 while(!q.empty()) { x=q.front(); q.pop(); for(int j=1;j<=m;j++) { t=x+b[j]; if(t>n+1||vis[t]) continue; //往后走，注意t>n+1才不能走 dis[i][t]=dis[i][x]+1; q.push(t); vis[t]=1; } for(int j=1;j<=m;j++) { t=x-b[j]; if(t<=0||vis[t]) continue; //往前走 dis[i][t]=dis[i][x]+1; q.push(t); vis[t]=1; } } for(int j=1;j<=tot;j++) if(i!=j) p[i][j]=dis[i][pos[j]]; //处理p数组 } } int f[1<<18],c[M],d[M]; int main() { int a; n=read(); K=read(); m=read(); for(int i=1;i<=K;i++) a=read(),c[a]=1; for(int i=1;i<=m;i++) b[i]=read(); for(int i=1;i<=n+1;i++) d[i]=c[i-1]^c[i]; for(int i=1;i<=n+1;i++) if(d[i]) pos[++tot]=i;//求出差分序列中每个1的位置 pre_BFS(); memset(f,63,sizeof(f)); f[0]=0; int mx=(1<<tot)-1,cnt; for(int i=0;i<mx;i++) { cnt=0; for(int j=0;j<tot;j++) cnt+=(i>>j)&1; if(cnt&1) continue;//判断如果状态有奇数个一，那么怎么消都消不掉 for(int j=0;j<tot;j++)//找到第一个1 { if((i>>j)&1) continue; for(int k=j+1;k<tot;k++)//枚举其他的1 if(!((i>>k)&1)) f[i|(1<<j)|(1<<k)]=min(f[i|(1<<j)|(1<<k)],f[i]+p[j+1][k+1]);//注意如果不能走，p不要设太大，可能爆int break;//找到后就break掉 } } printf("%d",f[mx]); return 0; }