题解 P3943 【星空】

一道隐藏得十分隐蔽的状压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的差分数组对应的原串全是1ORZ。

妙处二

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

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

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

举个例子:

​ 若操作的长度为4,1，原序列为1000：

原串	差分数组
1000	11000
0111	01001
1111	00000

距离为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,也就是无解。

为什么呢?

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

但$(5-4+5-4)$的决策是上面跑不出来的，$(5+5-4-4)$又超出了背包的范围。 代价计算的残缺就可能造成结果的错误。 但假定我们解决的上面的问题，仍然是错的QAQ。 再来看看下面这组数据： ```cpp 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吧。

## 正确的代码 ```cpp #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; } ```