学步园

http://www.codeforces.com/problemset/problem/212/C

不错的一个DP题，重在思维。（YY了大神的代码良久）

题意：给你一串由A 和 B组成的字符串，首尾是相连的，组成一个环

有个规则就是AB 会 变成BA，然后问你有多少个串可以一步变成给你的串

比如 BAA

答案是1，只有ABA一个串可以变成BAA

讲一下解法吧，首先，环状的东东就要想办法先破环，怎么破环呢？由于AB可以变成BA，反过来不行，而环状的字符串，以任意一个字符开头都是一样的，我们可以假设一下，加入以A开头，如果最后一个字符是B，那么  第一个字符是B最后一个字符是A
 这样的串可以变成给定的串，而  第一个字符是A最后一个字符是B  这样的串也可以变成给定的串，所以没有办法确定第一个字符是什么，也就没办法转换成线性序列。

所以我们应该以B开头，因为没有什么串会变成  【 ？B 】 即在这种情况下，不管你构造的串的最后一个字符是什么，第一个字符始终是B，这样我们就将序列的第一个字符定下来了。

最后就是递推的过程了.枚举最后以A结尾还是以B结尾 再从给定串的开头一直推到结尾

分情况讨论，

如果给定串当前字符是B，

               那么构造的字符串上一个字符只能是B，如果是A的话就要变成BA了，不合法

如果给定串当前字符是A，

              如果上一个字符是B，那么在构造串中这两个字符就可以是AB（以B结尾），或者以A结尾

             否则（最后两个字符为AA），那么构造串中当前字符只能以A结尾了（以B结尾的话，可以通过AB变成BA，但当前最后两个字符就变成BA了）

           看了代码后 ， 可能有的人会奇怪，给定串中当前最后两个字符是 BA 时，为什么 dp[i+1][1]=dp[i][0]+dp[i][1];dp[i][1] （上一层状态）不是表示最后一个字符为A吗，上一个字符明明是B，是这样的，dp[i][j]的状态是表示已经满足了构造前i个字符经过一步会变成给定串的前i个字符，所以前面的已经满足了，只需要关心当前的字符，让当前的字符也满足条件即可

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long gao(int n,int tag,int a[]){//dp[i][j]：前i个字符在满足条件的情况以j结尾的数量，字符 为“A” 时j==1
	long long dp[110][2]={};
	dp[0][tag]=1;
	for(int i=0;i<n;i++){
		if(!a[i+1]){//这个时候不需要求解1状态，因为不会变成（。B），只有AB->BA
			dp[i+1][0]=dp[i][0];
		} else {
			if(a[i]){ 
			     dp[i+1][1]=dp[i][0]+dp[i][1];
			}else {
				 dp[i+1][0]=dp[i-1][0]+dp[i-1][1];// AB->BA
				 dp[i+1][1]=dp[i][0]+dp[i][1];
			}
		}
	}
	return dp[n][tag];
}
int main()
{
	char s[110];
	int n=strlen(gets(s)),a[110];
	int pos=strcspn(s,"B");
	if(pos>=n-1) return puts("1"),0;
	for(int i=0;i<n;i++) a[i+1]= (s[(i+pos)%n]=='A');
	return printf("%I64d\n",gao(n,0,a)+gao(n,1,a)),0;
}