问题标题: 酷町堂：3660 又是翻硬币

3660   又是翻硬币

题目描述 Description

现在有一排硬币，正面朝上的用1表示，背面朝上的用0表示。现在要求从这行的第一个硬币开始，将n个硬币（1≤n≤硬币个数）一起翻面，问如果要将所有硬币翻到正面朝上，最少要进行这样的操作多少次？

输入描述 Input Description

一个字符串长度小于100000，仅由0和1组成

输出描述 Output Description

要翻转的最少次数。

样例输入 Sample Input

10

样例输出 Sample Output

2

数据范围及提示 Data Size & Hint

样例说明：

第1次翻转：把第一个硬币翻到反面，字符串为00

第2次翻转：把第一、二个硬币一起翻到正面，字符串为11，翻转完成，输出2

我的MLE：

#include<bits/stdc++.h>
using namespace std;

int n;
string s;
int ret=0x7f;
bool mark[100010];

bool pd(bool num[]){
    for(int i=1;i<=n;i++){
        if(num[i]!=true) return false; 
    }
    return true;
}

void f(int yuan,bool reft[],int cnt){
    if(pd(reft)){
        ret=min(ret,cnt);
        return ;
    }
    for(int i=1;i<=n;i++){
        reft[i]=!reft[i];
        if(i!=yuan) f(i,reft,cnt+1);
    }
    return ;
}

int main(){
    cin>>s;
    n=s.length();
    for(int i=0;i<s.length();i++){
        if(s[i]=='1') mark[i]=true;
        else mark[i]=false;
    }   
    f(0,mark,1);
    cout<<ret;
    return 0;
} 

PS：不一定用搜索