题解：P13832 【MX-X18-T4】「FAOI-R6」绿茶
Him_shu
·
·
题解
背景
考场会做，调到现在，因为小错误浪费三个小时，劝大家错了用对拍调试。
这题我认为应该凭绿更恰当一点。
题意
你有两个 n 位二进制数 A,B（可能有前导 0）和一个序列 c_0, c_1, \ldots, c_{n - 1}。
花费 c_k 的代价让 A 或上 A+2^K 或 A-2^K。
求 A 变成 B 的最小代价，不行就输出 -1。
分析
因为 A 每次只能变大，二进制包含 A 的肯定可以达到，所以当存在 k 有 A_k>B_k 则输出 -1，否则肯定可以达到。
::::info[代码]
for(int i=0;i<n;i++)
if(s1[i]>s2[i]){puts("-1");return;}
::::
先考虑 B 是全 1 的情况。
之后我们考虑如何变 A。
问题1：一开始我们想是不是每一位空的加上 c^k 解决，就是最优呢？
回答1：
其实不一定，样例
6
001001
111111
8 4 7 3 6 2
就是反例，明显从小到大，有空的直接加上 1，考虑进位所以每一位都能或上。
想这样做：
001001+1=001010
相或=001011
001011+1=001100
相或=001111
这样子对于前面的明显更优。
问题2：难道这个已经是答案了吗？
回答2：No！我们都没有考虑花费 c_k 的代价让 A 或上 A-2^K 的情况。
那么如何解决？玩一下样例便知
10
0000000000
1111111111
1 1 4 5 1 4 1 9 1 9
一位一位的操作明显不优，是不是可以对最高位加个 1 再对 最低位减个 1 实现用两个操作实现对整个的修改，具体可以看下面。
0000000000+1000000000=1000000000
相或=1000000000
1000000000-1=0111111111
相或=1111111111
考虑到低位不好被高位修改，所以可以从低往高走，可以考虑 DP。
状态：dp_i 表示前 i 位已经复原的最小代价。
转移：分两种情况：
- 从 i-1 通过回答1的方式转移 dp_i=dp_{i-1}+minc
- 从 j<i 通过回答2的方式转移 dp_i=\min(dp_j+c_{j+1}+c[i])，j 到 i 没有 1 在 A 中。
前面说是先考虑 B 是全 1 的情况。
## Code
暴力：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5,mod=998244353,inf=1e14;
int n;
int c[N];
string s1,s2;
int dp[N];
void work(){
cin>>n;
cin>>s1>>s2;
reverse(s1.begin(),s1.end());
reverse(s2.begin(),s2.end());//方便从低到高，当然不变也可以
s1[n]=s2[n]='0';//在最后分段
for(int i=n-1;i>=0;i--)
cin>>c[i];
for(int i=0;i<n;i++)
if(s1[i]>s2[i]){puts("-1");return;}//判-1
int ans=0;
memset(dp,0,sizeof(dp));
dp[0]=(s1[0]!=s2[0])*c[0];
for(int i=1;i<=n;i++){
if(s2[i]=='0'){
ans+=dp[i-1];
dp[i]=0;
continue;
}//分段
if(s1[i]=='0'){
int mi=inf;
for(int j=i;j>=0&&s2[j]=='1';j--)
mi=min(mi,c[j]);
dp[i]=dp[i-1]+mi;//通过回答1的方式转移
for(int j=i-2;j>=-1&&s2[j+1]=='1'&&s1[j+1]=='0';j--)
dp[i]=min(dp[i],(j<0?0:dp[j])+c[j+1]+c[i]);
//通过回答2的方式转移
}
else{
dp[i]=dp[i-1];//已经相同回答1的方式转移可以继承上一个
for(int j=i-2;j>=-1&&s2[j+1]=='1'&&s1[j+1]=='0';j--)
dp[i]=min(dp[i],(j<0?0:dp[j])+c[j+1]);//同理
}
}
cout<<ans<<"\n";
}
signed main(){
int _;
cin>>_;
while(_--)work();
return 0;
}
```
考虑到都是连续的所以可以用变量一遍枚举位的时候，一遍统计，遇到分段要从新搞。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5,mod=998244353,inf=1e14;
int n;
int c[N];
string s1,s2;
int dp[N];
void work(){
cin>>n;
cin>>s1>>s2;
reverse(s1.begin(),s1.end());
reverse(s2.begin(),s2.end());
s1[n]=s2[n]='0';
for(int i=n-1;i>=0;i--)
cin>>c[i];
for(int i=0;i<n;i++)
if(s1[i]>s2[i]){puts("-1");return;}
int ans=0;
memset(dp,0,sizeof(dp));
int mi=c[0],mi_dp=(s1[0]=='0'?c[0]:inf);
//mi对于回答1的方式转移做统计
//mi_dp对于回答2的方式转移做统计
//下面同理
for(int i=0;i<=n;i++){
if(s2[i]=='0'){
ans+=(i<1?0:dp[i-1]),
mi=inf,mi_dp=c[i+1];
continue;
}
mi=min(mi,c[i]);
if(s1[i]=='0')
dp[i]=min(mi_dp+c[i],dp[i-1]+mi),
mi_dp=min(mi_dp,dp[i-1]+c[i]);
else
dp[i]=min(dp[i-1],mi_dp),
mi_dp=inf;
}
// for(int i=0;i<n;i++)cout<<dp[i]<<' ';
cout<<ans<<"\n";
}
signed main(){
int _;
cin>>_;
while(_--)work();
return 0;
}
```