传送门：http://www.rqnoj.cn/Problem_165.html

f[i]表示前i个有多少个FBI

g[i]表示前i个有多少个FB

t[i]表示前i个有多少个F

假设现在到第i位

如果ch[i]=='F'

f[i]=f[i-1],g[i]=g[i-1],t[i]=t[i-1]+1；

如果ch[i]=='B'

f[i]=f[i-1],g[i]=g[i-1]+t[i-1],t[i]=t[i-1]

如果ch[i]=='I'

f[i]=f[i-1]+g[i-1],g[i]=g[i-1],t[i]=t[i-1]

时间复杂度:O(n)

Code

1 #include 
      
        2 using namespace std; 3  4 string s; 5 int f[2100],g[2100],t[2100]; 6  7 int main() 8 { 9     freopen("in.txt","r",stdin);10     freopen("out.txt","w",stdout);11     12     cin>>s;13     for(int i=1;i<=s.size();i++)14     {15         if( s[i-1] == 'O' )16             f[i]=f[i-1],g[i]=g[i-1],t[i]=t[i-1];17         else if( s[i-1] == 'F' )18             f[i]=f[i-1],g[i]=g[i-1],t[i]=t[i-1]+1;19         else if( s[i-1] == 'B' )20             f[i]=f[i-1],g[i]=g[i-1]+t[i-1],t[i]=t[i-1];21         else if( s[i-1] == 'I' )22             f[i]=f[i-1]+g[i-1],g[i]=g[i-1],t[i]=t[i-1];23     }24     cout<
       
        <