Codeforces 79D - Password（状压 dp+差分转化）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

Codeforces 题目传送门 & 洛谷题目传送门

一个远古场的 *2800，在现在看来大概 *2600 左右罢（

不过我写这篇题解的原因大概是因为这题教会了我一个套路罢（

首先注意到每次翻转的是一个区间，那么我们可以考虑它的差分序列（这就是这题教会我的套路，碰到区间操作有关的问题不妨考虑它的差分序列，这样可将影响多个元素的区间操作转化为 \(2\) 个单点操作，其实第一次碰见这个套路是在这个题，可是由于当时比较 naive 没能及时补题并整理这些方法），那么每次操作显然是将差分序列上两个单点进行翻转，而翻转的两个单点的距离恰好等于操作区间的长度，于是现在问题转化为：你有一个初始为 \(0\) 的长度为 \(n+1\) 的序列 \(a\)，你可以选择两个单点并将它们的状态翻转，满足这两个单点的距离属于某个集合 \(S\)，要求最少多少次操作将序列变为给定序列 \(a'\)。

考虑怎样解决转化后的问题，首先取两个单点并翻转显然是不影响 \(1\) 的个数的奇偶性的，因此如果 \(1\) 的个数是奇数那直接 \(-1\) 即可，否则显然我们会将这些 \(1\) 两两配对，对于同一对中的两个位置 \(x,y\)，我们会以如下方式让 \(x,y\) 上的数都变为 \(0\)：

重复以下步骤若干次：

• 选择一个长度 \(l\in S\) 并将 \(x\) 与 \(x+l\) 或 \(x-l\) 同时翻转，这样即可将 \(x\) 上的 \(1\) 转移到 \(x+l\) 或 \(x-l\) 上。

直到 \(x+l=y\lor x-l=y\)

我们记 \(d_{x,y}\) 为将 \(x,y\) 上的数变为 \(0\) 的最小步骤，那么显然我们可以以每个 \(1\) 为起点进行一遍 BFS 求出所有 \(d_{x,y}\)。注意到此题 \(k\le 10\)，因此差分序列上 \(1\) 的个数 \(\le 20\)，故考虑状压 \(dp\)，\(dp_S\) 表示将 \(S\) 中的 \(1\) 变为 \(0\) 的最小代价，转移就枚举两个 \(x,y\notin S\) 然后 \(dp_{S\cup\{x\}\cup\{y\}}\leftarrow dp_S+d_{x,y}\) 即可。

据说有更优秀的二分图最小权完美匹配的做法？i 了 i 了，可惜我懒癌爆发懒得写了

复杂度 \(2^kk^2+nmk\)，其中 \(k=20\)。

const int MAXN=1e4;
const int MAXM=100;
const int MAXK=20;
const int MAXP=1<<20;
const int INF=0x3f3f3f3f;
int n,k,m,a[MAXN+5],b[MAXN+5],l[MAXM+5],id[MAXN+5],pos[MAXK+5];
int dis[MAXN+5],d[MAXK+5][MAXK+5],cnt;
void bfs(int s){
queue<int> q;memset(dis,-1,sizeof(dis));
dis[s]=d[id[s]][id[s]]=0;q.push(s);
while(!q.empty()){
int x=q.front();q.pop();
if(id[x]) d[id[s]][id[x]]=dis[x];
for(int i=1;i<=m;i++){
if(x+l[i]<=n+1){
if(!~dis[x+l[i]]) dis[x+l[i]]=dis[x]+1,q.push(x+l[i]);
} if(x-l[i]>=1){
if(!~dis[x-l[i]]) dis[x-l[i]]=dis[x]+1,q.push(x-l[i]);
}
}
}
}
int dp[MAXP+5];
int main(){
scanf("%d%d%d",&n,&k,&m);
for(int i=1,x;i<=k;i++) scanf("%d",&x),a[x]=1;
for(int i=1;i<=m;i++) scanf("%d",&l[i]);
for(int i=1;i<=n+1;i++) b[i]=a[i]^a[i-1];
for(int i=1;i<=n+1;i++) if(b[i]) id[i]=++cnt,pos[cnt]=i;
memset(d,63,sizeof(d));
for(int i=1;i<=n+1;i++) if(id[i]) bfs(i);
memset(dp,63,sizeof(dp));dp[0]=0;
//printf("%d\n",cnt);
//for(int i=1;i<=cnt;i++) for(int j=1;j<=cnt;j++)
//printf("%d%c",d[i][j]," \n"[j==cnt]);
for(int i=0;i<(1<<cnt);i++){
if(dp[i]>=INF) continue;
for(int j=1;j<=cnt;j++) for(int l=1;l<j;l++)
if((~i>>j-1&1)&&(~i>>l-1&1))
chkmin(dp[i|(1<<j-1)|(1<<l-1)],dp[i]+d[j][l]);
} printf("%d\n",(dp[(1<<cnt)-1]>=INF)?-1:dp[(1<<cnt)-1]);
return 0;
}