本課程是從少年編程網轉載的課程，目標是向中學生詳細介紹計算機比賽涉及的程式語言，數據結構和算法。編程學習最好使用計算機，請登陸 www.3dian14.org (免費註冊，免費學習)。
給定一個字符串，統計形式為a^i b^j c^k()的子序列數，即由i個'a'字符，後跟j個'b'個字符，然後再跟k個'c'個字符組成，其中i>=1，j>=1和k>=1。
注意：即使兩個子序列相同，只要兩個子序列中至少有一個字符來自於原字符串的不同位置，也認為這兩個子序列是不同的。
【例子1】
輸入 : abbc
輸出 : 3
符合條件的子序列：abc, abc 和 abbc。注意，兩個abc中的b分別來自於原字符串的第二位置和第三個位置。
【例子2】
輸入 : abcabc
輸出 : 7
符合條件的子序列：abc, abc, abbc, aabc, abcc, abc 和 abc
算法
我們遍歷給定的字符串s。對於每個遇到的字符，執行以下操作：
1）設變量aCount為由'a'的不同組合產生的不同子序列的計數。初始化為0。
2）設變量bCount為由'b'的不同組合產生的不同子序列的計數。初始化為0。
3）設變量cCount為由'c'的不同組合產生的不同子序列的計數。初始化為0。
4）遍歷給定字符串的所有字符。對當前字符s[i]執行以下操作
如果當前字符是'a'，則存在以下可能性：
a）當前字符'a'開始一個新的子序列；
b）取當前字符'a'添加在已有aCount子序列末尾；
c）捨去當前字符'a'，也就是不把它作為aCount子序列的一部分。
因此，aCount =（1 + 2 * aCount）;
如果當前字符為'b'，則存在以下可能性：
a）當前字符'b'以aCount子序列（此時序列中僅僅包含字符'a')開始b的新子序列。
b）取當前字符'b'添加在已有bCount子序列末尾；
c）捨去當前字符'b'，也就是不把它作為bCount子序列的一部分。
因此，bCount =（aCount + 2 * bCount）;
如果當前字符為'c'，則存在以下可能性：
a）當前字符'c'以bCount子序列(此時序列中僅僅包含字符'a'和'b')開始c的新子序列。
b）取當前字符'c'添加在已有cCount子序列末尾；
c）捨去當前字符'c'，不把它作為 cCount子序列的一部分。
因此，cCount =（bCount + 2 * cCount）;
5）最後我們返回cCount，它就是最後的結果。
我們用例子來說明該算法:
aCount是字母「 a」的子序列數。
考慮以下示例：aa。
我們可以看到aCount為3：因為我們可以選擇以下可能性：（xa，ax，aa）（x表示我們沒有使用該字符）。還要注意，這與兩個'a'之間的字符無關，即'aa'的aCount和'ccbabbbcac'的aCount是相同的，因為它們的正好都包含2個a。
現在，加上1個'a'，記住此時之前由字符'a'組成的子序列數為aCount。對應新增加的字符'a', 我們有三種選擇：
i）還是每個之前由a組成的子序列，不取新增加的'a', 共有aCount個
ii）每個之前由a組成的子序列+新的字符'a' 組成新序列，共有aCount個
iii) 單獨由這裡新增加的字母'a'開始的新序列，個數為1
因此，增加一個'a', 新的僅有a組成的子序列數為：aCount + aCount + 1。
現在，讓我們考慮bCount，即幾個'a'之後接幾個'b'組成的子序列數。在"aab"中，我們看到bCount應該為3（對應的序列為axb，xab，aab, x表示沒有使用字符），因為它就是開始是兩個'a'的子序列，再加上'b'。因此，此時bCount的值就等於aCount。
現在我們再增加字符'b', 讓我們找到"aabb"的bCount。我們已經確定"aab"具有3個子序列，因此我們當然仍然具有這些子序列。此外，我們可以將新的b添加到這些子序列中的任何一個上，再次獲得3個新的子序列。最後，我們必須計算在不使用任何其他b的情況下產生的子序列，也就是aa加上當前的b組成的新序列（當前字符b是序列中的第一個字符b)，根據上一段中的邏輯，這就等於是aCount。因此，bCount就是舊的bCount * 2 + aCount；
cCount的計算過程與bCount類似。
下面幾個示意圖依次展示了針對字符串"aabbc"計算aCount,bCount和cCount的過程。
算法實現
下面是算法實現的例子。
#include <bits/stdc++.h>
using namespace std;
int countSubsequences(string s)
{
int aCount = 0;
int bCount = 0;
int cCount = 0;
// 遍歷字符串
for (unsigned int i=0; i<s.size(); i++)
{
if (s[i] == 'a')
aCount = (1 + 2 * aCount);
else if (s[i] == 'b')
bCount = (aCount + 2 * bCount);
else if (s[i] == 'c')
cCount = (bCount + 2 * cCount);
}
return cCount;
}
// 主程序
int main()
{
string s = "aabbc";
cout << countSubsequences(s) << endl;
return 0;
}
請你輸入程序，運行並驗證結果。一旦明白了算法，編程是不是佷簡單？