1208. 翻硬币

题目链接

思路

可以看成是开关问题，

1. 不一样的按一次
2. 每个只按一次
3. 从前往后

不理解的地方：这是怎么想出来的呢，为什么非得是从前往后就能保证是最优解呢…

代码

#include
using namespace std;
string a, b;
void turn(int i)
{
	if (a[i] == '*') a[i] = 'o';
	else if (a[i] == 'o') a[i] = '*';
}
int main()
{
	cin >> a >> b;
	int res = 0;
//	如果不一样就变
//	同时影响后一个 
	for (int i = 0; i < a.length() - 1; i ++ )
	{
		if (a[i] != b[i])
		{
			turn(i);
			turn(i + 1);
//			cout << a << endl << b << endl << endl; 
			res ++;
		}
	}
	cout << res;
	return 0; 
 } 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27