Clockwork（贪心）

题目描述
Rabbits are small mammals in the family Lep or idae of the or der Lagom or pha. So says Wikipedia.
C or rectly. The c or ollary is that they are not b or ing, f or they are all or iginal and well or ganized.
The rabbits on our farm live in guarded corrals whose borders are adorned with elaborate floral ornaments. Scores of adorable orange carrot clumps grow in the corrals. Rabbits reproduce quickly (it is a norm, hordes of rabbits are born each year) and our mentors are keen to locate them in the corrals effortlessly.
The corrals are well-ordered, they form one straight row of corrals. At the beginning of the first breeding season, some corrals may be unoccupied by rabbits. At the end of each breeding season, a well orchestrated relocation of rabbits is performed. The relocation is guided by a simple formula which depends on one positive integer parameter K , which may be chosen arbitrarily for each season. The relocation works on all corrals in parallel. In each corral,approximately one half of rabbits are removed from the corral and moved K corrals down the row of the corrals. It does not matter whether the target corral is already occupied by some rabbits or not.
If a corral is too close to the end of the row (there are less than K corrals down the row of corrals) then all the rabbits stay in the corral and are not moved anywhere.
Any corral can accommodate unlimited number of rabbits and there are always enough rabbits to breed successfully in any nonempty corral.
You are given a specification of which corrals are occupied and which are empty at the beginning of the first breeding season. Determine the minimum number of relocations needed to populate all corrals by rabbits.

输入
Input consists of a single line with a string of b characters (1 ≤ b ≤ 40), each representing one corral and being either 0 (empty corral) or 1 (inhabited corral). The first character corresponds to the first corral in the row.

输出
Output the minimum number of relocations needed to populate all corrals. If it is not possible to populate all corrals by any number of relocations, print −1.

样例输入
1010

样例输出
1

思路
每次贪心找到搬的最优方法，直至结束，当第一栏为0时，解必为-1

代码实现

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 100;

char s[N];
bool line[N];
int sum[N];
int l;
int check()
{
    for(int i=1;i<=l;i++) if(!line[i]) return i;
    return 0;
}
void moved(int x)
{
    int maxn=-1,tmpn=0;
    for(int i=1;i<=x;i++)
    {
        int cnt=0;
        for(int j=1;j<=l-i;j++)
        {
            if(!line[j+i] && line[j]) cnt++;
        }
        if(cnt>maxn)
        {
            maxn=cnt;
            tmpn=i;
        }
    }
    for(int i=l-tmpn;i>0;i--)
    {
        if(!line[i+tmpn] && line[i]) line[i+tmpn]=true;
    }
}
int main()
{
    scanf("%s",s);
    l=strlen(s);
    for(int i=0;i<l;i++) if(s[i]=='1') line[i+1]=true;
    int ans=0;
    if(!line[1]) printf("-1\n");
    else
    {
        while(1)
        {
            int p=check();
            if(p==0) break;
            moved(p);
            ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}