題目描述：
有一個長度為100的只含A和B的環(huán)行串。如果這個串含有AB，那么就變?yōu)锽A。 給一個串，問有多少種串可以變?yōu)檫@個串。
算法分析：
我們只關(guān)心ABABAB...ABAB這樣的串。在原串中把這樣的子串全都抽出來，再把方案數(shù)相乘就可以了。
如果成環(huán)的話，那么預(yù)處理出所有情況。遞推就可以了，是組合數(shù)學(xué)中非常經(jīng)典的遞推式。
如果不成環(huán)，有四種情況。分別為
1. ABAB
2. BABA
3. ABABA
4. BABAB
3和4是一種情況，剩下兩個是一種情況。利用預(yù)處理的結(jié)果計算就可以了。時間復(fù)雜度O(n)。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
ll dp[100][2],d[100][2][2];
char ch[205];
int vis[205];
int main(){
static ll clr[100];
dp[0][1] = dp[1][1] = dp[1][0] = 1;
for(int i=2;i<=50;i++)
dp[i][0] = dp[i-1][1],
dp[i][1] = dp[i-1][1] + dp[i-1][0];
d[1][1][1] = 1;
d[1][0][0] = 1;
d[2][0][1] = 1;
d[2][1][0] = 1;
d[2][1][1] = 1;
for(int i=3;i<=50;i++){
d[i][0][1] = d[i-1][0][1] + d[i-2][0][1] ;
d[i][0][0] = 0;
d[i][1][0] = d[i-1][1][1];
d[i][1][1] = d[i-1][1][1] + d[i-1][1][0];
}
for(int i=1;i<=50;i++)
for(int a=0;a<2;a++)
for(int b=0;b<2;b++)
clr[i] += d[i][a][b];
// for(int i=1;i<=50;i++) cout<<clr[i]<<" "; cout<< endl;
// main
while(~scanf("%s",ch)){
memset(vis,0,sizeof(vis));
ll ans = 1;
int n = strlen(ch);
for(int i=0;i<n;i++)
ch[n+i] = ch[i];
int s = 0;
if(ch[s]!=ch[n-1])while(ch[s]!= ch[s+1] && s < n-1) s ++;
for(;s<n;) {
int ed = s;
while(ch[ed]!=ch[ed+1] && ed-s+1 < n) ed ++;
int tmp = ed-s+1>>1;
if(n%2==0 && ed-s+1 == n) {ans = clr[n/2];break;}
if(ch[ed] == ch[s]) ans *= dp[tmp][1];
else if(ch[s] == 'A' ) {
tmp -= 1;
if(tmp == 0) {ans = 0;}
else if(tmp > 2) ans *= dp[tmp-1][1];
}
else ans *= dp[tmp][0] + dp[tmp][1];
//cout<<s<<" "<<ed<<" "<<ans<<endl;
s = ed + 1;
}
cout<< ans << endl;
}
}
posted on 2012-07-29 18:41
西月弦 閱讀(372)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告