P8597 [蓝桥杯 2013 省 B] 翻硬币 题解

sw2022 · 2022-10-24 18:28:31 · 题解

题意简析

因为把相邻两个硬币翻转两次相当于不翻，所以最优方案中同一组硬币最多只会翻转一次，故翻转顺序无后效性，考虑贪心：从前往后比较，发现一个不同的硬币就把它和他后面的硬币翻转，计数器累加，这样最后累加结果一定是最优方案的次数。

代码/解释

#include<bits/stdc++.h>
using namespace std;
string a,b;
int main()
{
    cin>>a>>b;
    int l=a.size(),s=0,i;
    for(i=0;i<l;i++)
    if(a[i]!=b[i])
    {
        a[i]=a[i]=='o'?'*':'o';
        a[i+1]=a[i+1]=='o'?'*':'o';
        s++;
    }
    printf("%d\n",s);
    return 0;
}