题目：BZOJ3003.
题目大意：给定一个长度为n nn序列a i a_iai与给定m mm种操作，a i a_iai初始全为0 00，每种操作给定一个长度，表示可以对这个长度的区间取反.现在要你用一定次数的操作把整个序列变成只有k kk个位置为1 11，其余全为0 00，求最少操作数.
数据组数T ≤ 10 T\leq 10T≤10，1 ≤ n ≤ 1 0 4 , 1 ≤ m ≤ 100 , 1 ≤ k ≤ 10 1\leq n\leq 10^4,1\leq m\leq 100,1\leq k\leq 101≤n≤104,1≤m≤100,1≤k≤10.
对于这种区间染色的题，我们发现区间染色的操作非常麻烦，所以考虑把操作和序列都进行异或差分，现在操作变成相隔一定长度的两个位置取反，同时最终的序列变成了最多2 k 2k2k个位置为1 11.
之后考虑把问题变为从终态到初态的最少步数，然后状压DP.设f [ S ] f[S]f[S]表示集合S SS中的位置为1 11其它位置为0 00需要的最少步数，那么可以列出转移：
f [ S ] = min i , j ∉ S { f [ S ∪ { i , j } ] + g ( i , j ) } f[S]=\min_{i,j\notin S}\{f[S\cup\{i,j\}]+g(i,j)\}f[S]=i,j∈/Smin{f[S∪{i,j}]+g(i,j)}
其中g ( i , j ) g(i,j)g(i,j)表示把位置i ii和位置j jj同时消掉需要的最少步数，但是这个东西并不好求.
考虑若当前用长度为l e n 1 len_1len1的操作消掉了位置i ii，则位置i + l e n 1 i+len_1i+len1会变为1 11，之后用长度为l e n 2 len_2len2的操作消掉位置i + l e n 1 i+len_1i+len1，则位置i + l e n 1 i+len_1i+len1会变为0 00且i + l e n 1 + l e n 2 i+len_1+len_2i+len1+len2变为1 11…
我们会发现上述过程类似于一个最短路，对于每一个位置i ii和每一个区间长度j jj，则将位置i ii和i + j , i − j i+j,i-ji+j,i−j两个位置连接起来，跑个最短路就完事了.
一个小优化，容易发现每次转移的时候位置( i , j ) (i,j)(i,j)中有一个位置是可以钦定而不枚举的，这样就可以少O ( k ) O(k)O(k)的时间复杂度了.
时间复杂度O ( T ( n m + 2 2 k k ) ) O(T(nm+2^{2k}k))O(T(nm+22kk)).
代码如下：
#include<bits/stdc++.h>using namespace std;#defineAbigail inline voidtypedeflonglongLL;constintN=10000,M=100,K=10,INF=(1<<30)-1;intnum[(1<<K*2)+9];voidGet_num(){for(inti=0;i<=K*2;++i)num[1<<i]=i;}intn,m,sk,a[N+9],len[M+9];intp[K*2+9],cp;voidGet_p(){cp=0;for(inti=1;i<=n;++i)if(a[i])p[++cp]=i;}structside{inty,next;}e[N*M*2+9];intlin[N+9],cs;voidIns(intx,inty){e[++cs].y=y;e[cs].next=lin[x];lin[x]=cs;}voidIns2(intx,inty){Ins(x,y);Ins(y,x);}voidGet_graph(){for(inti=1;i<=n;++i)lin[i]=0;cs=0;for(inti=1;i<=m;++i)for(intj=1;j<=n;++j){if(j-len[i]>=1)Ins(j,j-len[i]);if(j+len[i]<=n)Ins(j,j+len[i]);}}queue<int>q;intdis[K*2+9][N+9],vis[N+9];voidBfs_dis(intid,intst){for(inti=1;i<=n;++i)dis[id][i]=INF,vis[i]=0;dis[id][st]=0;vis[st]=1;q.push(st);for(;!q.empty();){intt=q.front();q.pop();for(inti=lin[t];i;i=e[i].next)if(!vis[e[i].y]){dis[id][e[i].y]=dis[id][t]+1;vis[e[i].y]=1;q.push(e[i].y);}}dis[id][st]=INF;}intdp[(1<<K*2)+9];voidGet_dp(){for(intg=0;g<1<<cp;++g)dp[g]=INF;dp[(1<<cp)-1]=0;for(intg=(1<<cp)-1;g>0;--g){if(dp[g]==INF)continue;intt0=g&-g;if(g-t0==0)continue;for(inti=g-t0;i;i-=i&-i){intt1=i&-i;dp[g^t0^t1]=min(dp[g^t0^t1],dp[g]+dis[num[t0]+1][p[num[t1]+1]]);}}}Abigailstart(){Get_num();}Abigailinto(){scanf("%d%d%d",&n,&sk,&m);++n;for(inti=1;i<=n;++i)a[i]=vis[i]=0;for(inti=1;i<=sk;++i){intx;scanf("%d",&x);if(vis[x])continue;vis[x]=1;a[x]^=1,a[x+1]^=1;}for(inti=1;i<=m;++i)scanf("%d",&len[i]);}Abigailwork(){Get_p();Get_graph();for(inti=1;i<=cp;++i)Bfs_dis(i,p[i]);Get_dp();}Abigailouto(){printf("%d\n",dp[0]==INF?-1:dp[0]);}intmain(){intT;start();scanf("%d",&T);while(T--){into();work();outo();}return0;}
