题解 P2708 【硬币翻转】

anyway · 2017-10-29 17:17:04 · 题解

题目到底在说啥？

发题解是因为一开始没看懂题目，所以给像我一样的蒟蒻解释一下，顺便说一下我的做法。

读入表示硬币状态的字符串，要把硬币都翻到1。翻转有一定的规则，如果你要翻第i枚硬币，必须把1~i枚都翻转。问怎么翻才能用最少的次数得到全部为1的硬币序列。

既然是翻1~i的话，连续的0可以一次变为1，就可以当成一个0处理。但是如果0前有1，就要再操作一次把翻成0的1翻回去。当我们找到一个0，如果它前面也是0，我们可以不管它，和前面的0一起处理。如果它前面是1，就要翻2次纠正。要做到次数最少，我们就要使调整好的状态不受影响，所以应该从后向前搜索，而翻转后面的操作实际不影响前面的值，因为前面的硬币会翻2次回到原状态。最后要再判断一下第一枚硬币，如果是0再翻1次。

#include<cstdio>
#include<cstring>
int main()
{
    char c[202];
    int i,l,s=0;
    scanf("%s",c);
    l=strlen(c);
    for (i=l;i;i--)
        if (c[i]=='0'&&c[i-1]=='1') s+=2;
    if (c[0]=='0') s++;
    printf("%d",s);
    return 0;
}