【题解】翻硬币

竟然没有题解，是人太少了还是太简单了..不过还是把我的贴上去吧，第一次写题解比较随意看不懂见谅..
简单的深搜会超时，所以得优化递归代码。
由于翻硬币时只能翻相邻的两枚，所以两串的不同点个数只能是偶数，我们就可以把它们看成一个个只有两个不同点的子串用递归解决了。容易发现让两个不同点转换的步数就是坐标之差。

ac代码

#include <iostream>
#include <bits/stdc++.h>
#define Inf 1e7
using namespace std;

string a,b;
int ans=Inf;
int L;
int cmp[1005];

//检查从下标k开始的子串是否相同，相同则完成
bool check(int k)
{
    while(cmp[k]==0&&k<L)
    k++;

    if(k==L)
    return true;
    else
    return false;
}

void dfs(int k, int s)
{
    if(check(k))
    {
        ans=min(ans,s);
        return ;
    }

    //找到第一个不同点
    while(cmp[k]==0)
    k++;

    if(k>=L-1)
    return ;

    int k0=k;
    k++;

    //找到第二个不同点
    while(cmp[k]==0)
    k++;

    dfs(k+1,s+k-k0);
}

int main()
{
    cin>>a>>b;
    L=(int)a.length();

    //a,b串不同处标1
    for(int i=0;i<L;i++)
    if(a[i]==b[i])
    cmp[i]=0;
    else
    cmp[i]=1;

    dfs(0,0);

    cout<<ans<<endl;
}