题目

点这里QAQ

菜鸡的咆哮

一道隐藏得十分隐蔽的状压$DP$。

题意大致是给你一个01串,每次操作可以对规定区间长度的0,1进行交换。

问最少用多少次才能将串的每一位变为1。

妙处一

看到区间修改我们想到利用差分求解。

每一次操作都相当与对操作区间的每一位与一异或($1\hat{}1=0 \ \ \ 0\hat{}1=1$)

所以可以把原问题转变在差分数组$(dif)$上进行!

对$[L,R]$操作就等效于$dif[L]\hat{}1,dif[R+1]\hat{}1$

所以原问题转化为给你一个01串,每次操作可以将串中的两个$1$变为$0$,有一个与两个$1$距离相应的费用。

问最少花费多少才能将串的每一位变为$0$。

为什么要将差分数组全部变为$0$呢?

多举几个例子归纳一下可以发现全$0$的差分数组对应的原串全是$1$ORZ。

妙处二

上面说到消去差分数组中两个$1$所需要的费用与它们的距离$x$有关。

因为题目给我们限制了每次操作的区间长度,也就是$x-1$。

所以有些距离的两个$1$我们无法通过一次操作消去。

举个例子:

​ 若操作的长度为$4$,$1$,原序列为$1000$:

原串差分数组
100011000
011101001
111100000

距离为$3$的两个$1$需要由$4-1$转移得到。

所以我们要提前预处理出消去距离为$x$的两个$1$需要最少的操作次数。

不妨将k个可执行的区间长度抽象为$k$个体积为$len$的物品和$k$个体积为$-len$。

用最小的物品来填充背包,背包的大小就是消去距离为$x$的两个$1$需要最少的操作次数。

注意:不能将正负体积的物品放在一起DP,它们的转移顺序不同,要分两个写。

妙处三

利用背包处理完后,就可以愉快的状压$DP$了。

但是串的长度显然不符合状压的要求。

经过一番观察后我们发现最开始最多只有8个灯泡是熄灭的。

所以差分串中最多只有$16$个$1$。

好了,我们可以把所有的$1$单独提出来,记录它们在原串的位置(用于计算操作次数)。

对于一个状态,从左到右确定一个$1$的位置,再去枚举另一个$1$的位置。

最后输出$f[0]$即可。

注意:我们是将差分串中的$1$提出来状压,所以初状态全是$1$,末状态全是$0$。

代码

#include<bits/stdc++.h>
#define maxn 40005
#define Epworth return 0 
using namespace std;
int n,m,k,xx; 
int dif[maxn];
int pos[maxn],tail;
int len[maxn],cost[maxn];
int f[1<<17];
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++) cin>>xx,dif[xx]^=1,dif[xx+1]^=1;
    for(int i=1;i<=k;i++) cin>>len[i];
    for(int i=1;i<=n+1;i++){
        if(dif[i]) pos[++tail]=i;
    }
    memset(cost,0x3f,sizeof(cost));
    cost[0]=0;
    for(int i=1;i<=k;i++){
        for(int j=len[i];j<=n;j++){
            cost[j]=min(cost[j],cost[j-len[i]]+1);
        }
    }
    for(int i=1;i<=k;i++){
        for(int j=n-len[i];j>=0;j--){
            cost[j]=min(cost[j],cost[j+len[i]]+1);
        }
    }
    int all=(1<<tail)-1;
    memset(f,0x3f,sizeof(f));
    f[all]=0;
    for(int i=all;i>=0;i--){
        for(int j=1;j<=tail;j++){
            if(!((1<<(j-1))&i)) continue;
            for(int k=j+1;k<=tail;k++){
                if(!((1<<(k-1))&i)) continue;
                int x=~((~i)|(1<<(j-1))|(1<<(k-1)));
                f[x]=min(f[x],f[i]+cost[pos[k]-pos[j]]);
            }
        }
    }
    cout<<f[0]<<endl;
    Epworth;
} 

等等还没完!!!

好了,上面这个漏洞百出的代码已经可以AC这道题了。

但是对于某些数据,它是错误的。

下面让我们来批判一下上面的代码。

看看下面这组数据:

7 2 2
2 3
5 4
1001111
1000000
1111110
1100000
1111111

不难发现它可以通过4次操作把整个灯泡串点亮。

但上面跑出来是$INF$,也就是无解。

为什么呢?

因为在上面跑完全背包正负价值是分开跑的,结果是不完整的。

$4,5$能凑出$1$,当然也能凑出$2$。

但$(5-4+5-4)$的决策是上面跑不出来的,$(5+5-4-4)$又超出了背包的范围。

代价计算的残缺就可能造成结果的错误。

但假定我们解决的上面的问题,仍然是错的QAQ。

再来看看下面这组数据:

6 2 2
3 4
5 3

正确答案应该为$6$,但上面跑出来是2。

是的又错了(愈发怀疑AC的真实性)。

这又是为什么呢?

在完全背包中,我们只考虑了在序列长度的限制下能否凑出某个距离。

但没有考虑消去的两个$1$在序列中的实际位置。

在错误的代码中,我们计算出消除距离为$2$的两个$1$只需要操作两次$(5-3=2)$

但实际上$5$是执行不了的。

110011(0)
111100(1)
111111(0)

理想的状态下我们在最后一个灯泡后虚构了一个假灯泡协助操作,最后把它熄灭了。

但这明显是不被允许的。

但如果是这样却又可以了。

6 2 2
2 3
5 3

在差分串中两个$1$的距离并没有改变。

所以在本题中$1$的实际位置也会影响结果,不只是相对位置。

.......

经过一番思索,我们还是好好的BFS吧。

BFS是从每个一的实际位置出发判断它能到达的地方,故不会存在上面的问题。

正确的代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define maxn 40005
#define Epworth return 0 
using namespace std;
int n,m,k,xx; 
int dif[maxn];
int pos[maxn],tail;
int len[maxn];
int dist[maxn];
int cost[20][20];
int f[1<<17];
queue<int> q;
void bfs(int s){
    memset(dist,0x3f,sizeof(dist));
    q.push(pos[s]);
    dist[pos[s]]=0;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=1;i<=k;i++){
            int a=x-len[i];
            int b=x+len[i];
            if(a>=1&&dist[a]==inf){
                dist[a]=dist[x]+1;
                q.push(a);
            }
            if(b<=n+1&&dist[b]==inf){
                dist[b]=dist[x]+1;
                q.push(b);
            }
        }
    }
    for(int i=1;i<=tail;i++){
        if(dist[pos[i]]!=inf){
            cost[s][i]=dist[pos[i]];
        }
    }
}
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++) cin>>xx,dif[xx]^=1,dif[xx+1]^=1;
    for(int i=1;i<=k;i++) cin>>len[i];
    for(int i=1;i<=n+1;i++){
        if(dif[i]) pos[++tail]=i;
    }
    memset(cost,0x3f,sizeof(cost));
    for(int i=1;i<=tail;i++) bfs(i);
    int all=(1<<tail)-1;
    memset(f,0x3f,sizeof(f));
    f[all]=0;
    for(int i=all;i>=0;i--){
        for(int j=1;j<=tail;j++){
            if(!((1<<(j-1))&i)) continue;
            for(int k=j+1;k<=tail;k++){
                if(!((1<<(k-1))&i)) continue;
                int x=~((~i)|(1<<(j-1))|(1<<(k-1)));
                f[x]=min(f[x],f[i]+cost[j][k]);
            }
        }
    }
    cout<<f[0]<<endl;
    Epworth;
}