【動的計画】TopCoder SRM 555 CuttingBitString

大体の意味は1つの01列を一連の5のべき乗次方の子列に分けて、題意の叙述は簡潔で、1本のとても良い動態的な計画のテーマです.
We are in a distant future. After the downfall of mankind, the Earth is now ruled by fairies. The "Turing game Online"website is hot among fairies right now. On this website, everyone can play the programming puzzle "Turing game". Fairies love powers of 5, that is, the numbers 1, 5, 25, 125, 625, and so on. In the Turing game, the player is given a string of bits (zeros and ones). The ideal situation is when the string is represents a power of 5 in binary, with no leading zeros. If that is not the case, the fairy player tries to cut the given string into pieces, each piece being a binary representation of a power of 5, with no leading zeros. Of course, it may be the case that even this is impossible. In that case, the fairy player becomes depressed, and bad things happen when a fairy gets depressed. You, as one of the surviving humans, are in charge of checking the bit strings to prevent the bad things from happening. You are given a String S that consists of characters '0' and '1' only. S represents the string given to a player of the Turing game. Return the smallest positive integer K such that it is possible to cut S into K pieces, each of them being a power of 5. If there is no such K, return -1 instead.
 
マイソース:

#include<string>
#include<vector>
#include<algorithm>
#define MAXIMUM 99999

using namespace std;

class CuttingBitString{
	public:
		//get min using dynamic programming method
		int getmin(string s){
			int len=s.size();
			int goal[60];
			for(int i=0;i<len;i++){
				goal[i]=MAXIMUM;
			}
			for(int i=0;i<len;i++){
				//additional test
				if(isFit(s,0,i)==true){
					// 1 will be the minimum number
					goal[i]=1;
					continue;
				}
				for(int j=0;j<i;j++){
					//right substring is not power of 5
					if(isFit(s,j+1,i)==false)
						continue;
					///front substring is not power of 5
					if(goal[j]==MAXIMUM)
						continue;
					goal[i]=min(goal[i],goal[j]+1);
				}
			}//end external for loop
			//there is no solution
			if(goal[len-1]==MAXIMUM)
				return -1;
			return goal[len-1];
		}
		
		//return if this substring is the power of 5
		bool isFit(string s,int begin,int end){
			if(begin>end)
				return false;
			//long long data type is enough for this problem
			long long counter=0;
			for(int i=begin;i<=end;i++){
				if(s[i]=='0')
					counter=counter<<1;
				else if(s[i]=='1')
					counter=(counter<<1)+1;
			}
			if(counter==0)
				return false;
			//test whether it is the power of 5
			while(counter%5==0){
				counter=counter/5;
			}
			//the power of five will lead to 1 in the end
			if(counter==1)
				return true;
			return false;
		}
};

オフラインでテストしてみましたが、正しいと思います.具体的に興味があればTopCoderのサイトに行ってみてください.とても詳しく(これはTopCoderが伝統的なOJに比べて大きなメリットだと思いますが......)