新的字母表(攻下试验场825)
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.
(问题中文说明,翻译的比较笨拙,请见谅)
一国家决定新排他们字母表，无大写字母。他们要发布只有'B'和'A'组成的规定约束，在新字符表中此规定的第一个字母将回决定'a'是在'b'的(B before)前面还是后面(A after),第2个字符将会决定'b'和'c'，依此类推。比如"BAA"就指明'a'在'b'的前面，'b'在'c'的后面，'c'在'd'的后面。
没有甬道的字符不要，比如规定中有K个字符，那么新字母表就只有K+1个小写字母。(我注：如上面的BAA有3个字符，那么新表就有4个，也就是'd'后面的全被忽略)
创建一个名为Alphabet的类，此类含有一个名为choices方法，choices方法以"规定(decree)"作为参数输入，然后返回所有符合这个规定的新字母表的可能数，如果大于1,000,000,000可能，就返回-1
定义：
类名：Alphabet
方法：choices
参数类型：string
返回值类型：int
方法签名：int choices(string decree)
(确保choices为公有方法)
参数条件：
规定中的'B'和'A'总和必须大于等于1，小于等于25
举个例
输入："BAA"
返回：3
解释：因为根据规定（"BAA"）'a'在'b'的前面，'b'在'c'的后面，'c'在'd'的后面,所有符合这个规定的新字母表有3个：adcb、dacb和dcab .
-------------------------------------------------------------------------
此问题的算法如下:
using System;
class Alphabet
{
public static readonly Int32 MaxValue = 1000000000;
public static int choices(String decree)
{
Int32 all_pass =0,count = 0;
Int32[] father = new int[decree.Length+1];
Int32[] son = new int[decree.Length+1];
father[0] =1;
foreach(char aorb in decree)
{
all_pass = 0;
if (aorb=='B')
for(int i=count ;i>=0 ; i--)
{
son[i]=son[i+1]+father[i];
if((all_pass+=son[i])>MaxValue) return -1;
}
if (aorb=='A')
for (int i=0 ; i<=count ; i++)
{
son[i+1]=son[i]+father[i];
if((all_pass+=son[i+1])>MaxValue) return -1;
}
Array.Copy (son,father,son.Length);
Array.Clear(son,0,son.Length);
count++ ;
}
return all_pass;
}
}
/// 想交朋友就email 我:zhonghua@rinpak.com.cn
