题解：P13832 【MX-X18-T4】「FAOI-R6」绿茶
baibaieee
·
·
题解
题目分析
观察题目，\lvert A-C\rvert =2^k, 所以有两种情况。
-
C=A+2^k
当该位为 0 时，A \mathbin{\mathrm{or}} C 相当于将 A 中该位变为 1。
当该位为 1 时，A \mathbin{\mathrm{or}} C 相当于将 A 中该位之前的最后一个 0 的位置变为 1。
-
C=A-2^k
当该位为 0 时， A \mathbin{\mathrm{or}} C 相当于将 A 中该位到该位之前的最后一个 1 中的位置都变为 1。
当该位为 1 时，操作无效果。
所以原题的操作转化成为：
- 将某一位由 0 变为 1，花费的代价为该位到与它连续的 1 的最后一位的 c_i 的最小值。
- 将某一位到该位之前的最后一个 1 中的位置都变为 1，花费 c_i。（需要保证 A_i=0 且存在 j < i，A_i=1。）
处理过程
我们称 B 中连续的 1 的区间为“ 1 段”。
我们将每一段位于“ 1 段”的 A 取出，单独处理，设其为 [L,R]。
我们将该段的前导零与后面的序列分离。
- 先处理非前导零部分，设其为 [l,R]。
我们从后往前进行DP。
设 dp_{i,u} 表示将这个“ 1 段”末尾到第 i 位都变为 1 所需的最小花费，u 表示是否在当前是否使用过操作 2。
设 m_{l,r} 为 \min_{i=l}^{r} c_i。
若 A_i=1 ，则 dp_{i,0}=\min\{dp_{i+1,0},dp_{i+1,1}\}。（使用过操作二的影响到它前面的最后一个 A_i=1 就会失效。）
若 A_i=0 ，则 dp_{i,0}=dp_{i+1,0}+m_{i,R}， dp_{i,1}=\min\{dp_{i+1,1},dp_{i+1,0}+c_i\}。
- 对于前导零部分，我们设其区间为 [L,r]。
假设有一个位置 p ，我们在这上面先进行一次操作一。
$p$ 之前只能使用操作一，花费为 $\sum_{i=L}^{p-1}m_{i,R}$。（注意此处是区间 $[i,R]$ 的最大值。）
所以总花费为 $\sum_{i=L}^{p-1}m_{i,R}+c_p+\min\{dp_{p+1,0},dp_{p+1,1}\}$。
枚举位置 $p$ ，取最小值即可。
总时间复杂度 $O(n)$ 。
## 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
string s1,s2;
long long T,n,a[MAXN],c[MAXN],ans,dp[MAXN][2],m[MAXN];
void init_min(int l,int r){
m[r+1]=1145141919810LL;
for(int i=r;i>=l;i--)m[i]=min(m[i+1],c[i]);
}
long long solve_allz(int l,int r,int r2){
//cout<<"solve a_all_0 "<<l<<" "<<r<<endl;
init_min(l,r2);
long long ans=0,tmp=0;
for(int i=l;i<=r;i++)tmp+=m[i];
//for(int i=l;i<=r;i++)cout<<m[i]<<" ";
//cout<<tmp<<endl;
ans=tmp;
for(int i=l;i<=r+1;i++)dp[i][1]=dp[i][0]=1145141919810LL;
dp[r+1][0]=0;
for(int i=r;i>=l;i--){
dp[i][0]=dp[i+1][0]+m[i];
dp[i][1]=min(dp[i+1][1],dp[i+1][0]+c[i]);
tmp-=m[i];
//cout<<i<<" "<<tmp<<" "<<tmp+c[i]+min(dp[i+1][0],dp[i+1][1])<<endl;
ans=min(ans,tmp+c[i]+min(dp[i+1][0],dp[i+1][1]));
}
return ans;
}
long long solve(int l,int r){
//cout<<"solve b_all_1 "<<l<<" "<<r<<endl;
long long ans=0;
for(int i=l;i<=r+1;i++){
if(s1[i]=='1'||i==r+1){
if(i!=l)ans=solve_allz(l,i-1,r);
l=i;
break;
}
}
if(l>r)return ans;
for(int i=l;i<=r+1;i++)dp[i][1]=dp[i][0]=1145141919810LL;
dp[r+1][0]=0;
init_min(l,r);
for(int i=r;i>=l;i--){
if(s1[i]=='1')dp[i][0]=min(dp[i+1][1],dp[i+1][0]);
else{
dp[i][0]=dp[i+1][0]+m[i];
dp[i][1]=min(dp[i+1][1],dp[i+1][0]+c[i]);
}
}
ans+=dp[l][0];
//cout<<ans<<endl;
return ans;
}
int main(){
cin>>T;
while(T--){
cin>>n;
cin>>s1>>s2;
for(int i=1;i<=n;i++)cin>>c[i];
s1="0"+s1+"0",s2="0"+s2+"0";
bool flag=0;
for(int i=1;i<=n;i++){
if(s1[i]=='1'&&s2[i]=='0'){
flag=1;
break;
}
}
if(flag){
cout<<-1<<endl;
continue;
}
ans=0;
int fs=0;
for(int i=1;i<=n+1;i++){
if(s2[i]=='0'&&fs){
//cout<<fs<<" "<<i-1<<endl;
ans+=solve(fs,i-1);
fs=0;
}
if(s2[i]=='1'&&!fs)fs=i;
}
cout<<ans<<endl;
}
return 0;
}
```