問(wèn)題描述
牛牛在書(shū)上看到一種字符串叫做回文串,當(dāng)一個(gè)字符串從左到右和從右到左讀都是一樣的,就稱這個(gè)字符串為回文串徒探。牛牛又從好朋友羊羊那里了解到一種被稱為優(yōu)美的回文串的字符串,考慮一個(gè)長(zhǎng)度為N只包含大寫(xiě)字母的字符串,寫(xiě)出它所有長(zhǎng)度為M的連續(xù)子串(包含所有可能的起始位置的子串,相同的子串也要計(jì)入),如果這個(gè)字符串至少有K個(gè)子串都是回文串,我們就叫這個(gè)字符串為優(yōu)美的回文串。現(xiàn)在給出一個(gè)N,牛牛希望你能幫他計(jì)算出長(zhǎng)度為N的字符串有多少個(gè)是優(yōu)美的回文串(每個(gè)位置都可以是'A'~'Z'的一個(gè)弹灭。)
輸入描述
輸入數(shù)據(jù)包括三個(gè)整數(shù)N, M, K(2 ≤ N ≤ 11, 2 ≤ M ≤ N, 0 ≤ K ≤ 11).
輸出描述
輸出一個(gè)整數(shù),表示所求的字符串個(gè)數(shù).
輸入例子
2 2 1
輸出例子
26
長(zhǎng)度為2的字符串,它長(zhǎng)度為2的子串只有它自身。長(zhǎng)度為2的回文串有"AA","BB","CC"..."ZZ",一共26種蛇损。
分析
假設(shè)有一個(gè)長(zhǎng)度為N的字符串S幕与，S有一個(gè)長(zhǎng)度為M的連續(xù)子串T。T包含了U種不同的字符价淌。T的每種不同的字符都可以被替換掉申眼，由于字符集為{A, B, C,...,Z}，所以總共有26*25*23*...*(27-U)種替換方法蝉衣。我們現(xiàn)在要做的括尸，就是在長(zhǎng)度為N的字符串集合中，枚舉所有長(zhǎng)度為M病毡、包含U種不同字符的字符串濒翻。
note
使用替換法，可以大大減少枚舉空間啦膜，提高效率有送。計(jì)算復(fù)雜度為O(n!)。n最大為11僧家，所以算法還是有可行性的雀摘。
代碼
#include <iostream>
#include <algorithm>
using namespace std;
int m, k, n;
char str[12];
long long fact[12], res = 0;
bool isElegantPalindrome()
{
int cnt = 0;
for (int i = 0; i < n - m + 1; i++)
{
bool flag = true;
for (int j = 0; j < m / 2; j++)
{
if (str[i + j] != str[i + m - 1 - j])
{
flag = false;
break;
}
}
if (flag)
cnt++;
}
return cnt >= k;
}
void dfs(int len, int typeNum)
{
if (len == 0)
{
if (isElegantPalindrome())
res += fact[typeNum];
return;
}
for (int i = 0; i <= typeNum; i++)
{
str[len - 1] = 'a' + i;
dfs(len - 1, max(typeNum, i + 1));
}
}
int main()
{
cin >> n >> m >> k;
fact[0] = 0; fact[1] = 26;
for (int i = 2; i <= n; i++)
fact[i] = fact[i - 1] * (27 - i);
dfs(n, 0);
cout << res << endl;
return 0;
}
