规则3.cpp

The government of a small but important country has decided that the alphabet needs to be streamline

/*
Problem Statement 
The government of a small but important country has decided that the alphabet needs to be streamlined and reordered. Uppercase letters will be eliminated. They will issue a royal decree in the form of a String of 'B' and 'A' characters. The first character in the decree specifies whether 'a' must come ('B')Before 'b' in the new alphabet or ('A')After 'b'. The second character determines the relative placement of 'b' and 'c', etc. So, for example, "BAA" means that 'a' must come Before 'b', 'b' must come After 'c', and 'c' must come After 'd'. 
Any letters beyond these requirements are to be excluded, so if the decree specifies k comparisons then the new alphabet will contain the first k+1 lowercase letters of the current alphabet. 
Create a class Alphabet that contains the method choices that takes the decree as input and returns the number of possible new alphabets that conform to the decree. If more than 1,000,000,000 are possible, return -1. 
Definition 
???? 
Class: 
Alphabet 
Method: 
choices 
Parameters: 
string 
Returns: 
int 
Method signature: 
int choices(string decree) 
(be sure your method is public) 
???? 

Constraints 
- 
decree contains between 1 and 25 characters inclusive. 
- 
Each character in decree is the upper case letter 'B' or 'A'. 
Examples 
0) 

???? 
"BAA" 
Returns: 3 
a before b, b after c, and c after d have been decreed, so possibilities are adcb, dacb, dcab 
1) 

???? 
"AAAA" 
Returns: 1 
edcba is the only alphabet that conforms 
2) 

???? 
"BABABABABABABABABABABABAB" 
Returns: -1 
More than 1,000,000,000 alphabets conform to this decree 
*/
//-------------------------------------------------------------------------------------------------------------------------------------------
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

class Alphabet
{
public: 
 long choices(string decree); 
};
 
template<typename T> class Init//清零
{
public:
	void operator ()(T & val)
	{
		val=0;
	}
};

long sum(vector<long> vl,int start, int end)
{
	long total=0;
	vector<long>::iterator vli;
	vli=vl.begin()+start;
	int i=end-start+1;
	while(i)
	{
		total += *vli;
		vli++;
		i--;
	}
//	cout<<total<<'\t';
	return total;
}
	
long Alphabet::choices(string decree)
{	
	Init<long> init;
	int countA=0,countB=0;
	int len=decree.length();
	int i,j;
	vector<long> vl(len+1);
	unsigned long total;
	
	for_each(vl.begin(),vl.end(),init);

	if('A'==decree[0])
	{	
		vl[0]=1;
		countA++;
	}
	else
	{
		vl[1]=1;
		countB++;
	}

//	current=1;
	
	for(i=1;i<len;++i)
	{
		if('A'==decree[i]) //case 'A'
		{
			
			for(j=0;j<=i-countA;++j)
			{   
			//	cout<<"v1["<<j<<"]=";
				vl[j]=sum(vl,j,i);
			}


			countB=0;
			countA++;
		}
		else     //case 'B'==vl[i]
		{
			countB++;

			for(j=i+1;j>=countB;--j)
			{
               // cout<<"v1["<<j<<"]=";
				vl[j]=sum(vl,0,j-1);
			}
			//while(j >= 0 )
			//{
			//	vl[j--]=0;
			//}
			vl[j]=0;
			countA=0;

		}

	}

    //cout<<"total=";
	total = sum(vl,0,len);
	/*vector<long>::iterator beg;
	//vector<long>::iterator end;
	int sum2=0,t=0;
	for(beg=vl.begin();beg<vl.end();beg++)
	{
		t++;
	  if(*beg>0)
	  {
	     cout<<"vl["<<t-1<<"]="<<*beg<<endl;
		 sum2+=*beg;
	  }
	}
	cout<<endl<<"sum2="<<sum2<<endl;
	*/
	return (total>1000000000L)? -1 : total;
}
void main()
{   
	string str;
	cin>>str;
	Alphabet b;
	cout<<endl<<b.choices(str);
	
}