首先,每个硬币只有两个状态,所以翻转的次数<=1
翻转奇数次不如翻转一次,翻转偶数次等于不翻转
顶多翻转len-1次(题目说了有解)
然后,讨论翻转的策略:
从头开始遍历,遇到不同的就翻转当前硬币和后一个硬币, 直到倒数第二个
首先遇到不同的硬币时一定要翻转,为什么不翻转当前的硬币和前一个硬币呢?
因为如果翻转前一个,相当于保持当前状态不变的情况下,去翻转前面的硬币,是无解的,故只能翻转当前的硬币
和后一个硬币,故上述策略就是最优策略
可能有点抽象,下面举一个例子:
00100010000
00000000000
re(i):表示翻转i、i + 1字符 1 <=i <= len - 1
0 <= re(i)<= 1
将第一个字符串翻转成第二个字符串
首先,顶多翻转9次(len = 10)
从头开始看,当在i = 3的位置,遇到 0 和 1 时,这个时候一定要翻转一个(re(2) ^ re(3) == 1)
要么翻转01(第一个字符串的2、3位置),要么翻转10(第一个字符串的3、4位置)
那么为什么不翻转01, 而选择翻转10呢?
因为如果翻转01,此时变为010 00010000
在保持re(2) == 1的情况下,翻转前面的硬币没办法使得达到该第二个字符串
故翻转10,故上述策略就是最佳策略
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 110;
char s1[N], s2[N];
void change(char &p)
{
if(p == 'o') p = '*';
else p = 'o';
}
int main ()
{
scanf("%s%s", s1, s2);
int len = strlen(s1);
int cnt = 0;
for(int i = 0; i < len - 1; i ++)
{
if(s1[i] != s2[i])
{
change(s1[i]);
change(s1[i + 1]);
cnt ++;
}
}
printf("%d\n", cnt);
return 0;
}
我这种小白都看懂了(手动滑稽)