翻转硬币(递推o(n))
一行硬币有正有反,每次操作只能翻转两个相邻硬币,给定初始和最终状态,求出初态到终态的最小操作次数
输入样例:
**********
o****o****
输出样例:
5
思路:从左到右,每个硬币最多只会被翻转1次,因此每个硬币是否需要翻转是唯一确定的,每个硬币前面的硬币是经过判断后固定不变的,只需要看本次是否需要翻转。从左到右枚举所有硬币,记录操作次数可得结果。
#include<iostream>
using namespace std;
string a, b;
void change(int i)
{
if(a[i] == '*') a[i] = 'o';
else a[i] = '*';
}
int main()
{
cin >> a >> b;
int res = 0;
for(int i = 0; i < a.size() - 1; i++) //题目保证一定有解,因此枚举到倒数第二个硬币即可
{
if(a[i] != b[i])
{
res++;
change(i), change(i+1);
}
}
cout << res;
return 0;
}