思路
乍一看......(好像也没什么)
仔细想想,不难发现(是个人都知道),一个硬币要翻转一定会使左右两边其中一枚硬币收到牵连......
再仔细想想,我们可以单一方向地进行牵连,这样的话不会使以前翻好的硬币重新翻......貌似是最优解(自信点,就是最优解)
c++代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+1e4;
string a,b;
ll ans,len;
signed main()
{
cin>>a>>b;
len=a.size();
for(ll i=0;i<=len-1;i++)
{
if(a[i]!=b[i])//判断是否要翻转硬币
{//这里我们就固定让右边的硬币受到牵连
if(a[i]=='o')a[i]='*';//翻转硬币
else a[i]='o';
if(a[i+1]=='o')a[i+1]='*';
else a[i+1]='o';
ans++;
}
}
cout<<ans;
}
y总说的比较麻烦复杂度比较高的dfs是怎么写的鸭,我老是联系不到实际应用里应该怎么写