随机字符串 题目描述 起名字什么的最麻烦，我们来生成一些随机字符串吧
生成的字符串当然是有要求的：
.长度不能超过n
.字符串中仅包含大写字母
.生成的字符串必须包含字符串“ACM” ok，是不是很简单？现在告诉你n的值，你来告诉我这样的字符串有多少个 输入 输入一个正整数T，代表有T组数据
接下来T行，每行一个正整数n，n<=。 输出 输出符合条件的字符串的数目 样例输入 样例输出
题解:
using namespace std;
#define inf 0x3f3f3f3f
#define N 110
#define ll long long ll dp[][]; ll dfs(int len,int st)
{
if(len<){
if(st==)return ;
return ;
}
if(dp[len][st]!=-)return dp[len][st];
ll s=;
for(char i='A';i<='Z';i++){
if(st==)
s+=dfs(len-,);
else if(i=='A')
s+=dfs(len-,);
else if(i=='C')
s+=dfs(len-, st==?:);
else if(i=='M')
s+=dfs(len-,st==?:);
else
s+=dfs(len-,);
}
dp[len][st]=s;
return s;
} int main(){ int T;
cin>>T;
memset(dp,-,sizeof(dp));
while(T--){
int n;
cin>>n; ll sum=;
for(int i=;i<=n;i++){
sum+=dfs(i,-);
}
cout<<sum<<endl;
} return ;
}
(超简洁!!超简洁!)