solution
题意简化
一个字符串，将所有的 _ 替换成大写字母，使结果字符串符合要求：
1、不包含三个连续 元音 或 辅音 字母；
2、字符串中至少有一个 L 。
求最终字符串可能的个数。
看到这道题，即想到了万能的算法——搜索。
从下标 开始，枚举每一个字母。
由于每次枚举的字母与后面的枚举无关，所以这样搜索不会出现重复的终串。
在枚举结束时使用 check 检测是不是合法终串，如果是就是一种情况。
可惜，只会拿到可怜的 的分数。
先来算算时间复杂度吧。
对于每次操作，都有每个 _ 需要枚举 次，同时最多有 位，所以枚举次数最少 次方，超时是稳稳的。
所以如何减少时间复杂度呢？
我们可以发现，这道题实际上**辅音字母之间并没有区别。**同理，对于元音字母也是如此。
所以，可以每次只枚举两次，对于辅音字母的结果乘 ；元音字母的结果乘 。
还有一点要注意，由于 L 会影响结果，所以需要特殊考虑。
总共 次，枚举次数降为 ，AC 稳稳的。
AC Code：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| #include<bits/stdc++.h>
using namespace std;
int yy[127];
int check(char ns[])
{
bool flag=0;
for(int i=0,len=strlen(ns);i<len-2;i++)
{
if((yy[ns[i]]==1&&yy[ns[i+1]]==1&&yy[ns[i+2]]==1)
||
((!yy[ns[i]])&&(!yy[ns[i+1]])&&(!yy[ns[i+2]]))) return -1;
if(!flag&&(ns[i]=='L'||ns[i+1]=='L'||ns[i+2]=='L')) flag=true;
}
return flag;
}
long long dfs(int i,char ns[])
{
int len=strlen(ns);
while(ns[i]!='_'&&i<len) i++;
if(i==len) return max(check(ns),0);
if(check(ns)==-1) return 0;
long long ans=0;
ns[i]='A';
ans+=dfs(i+1,ns)*5;
ns[i]='B';
ans+=dfs(i+1,ns)*20;
ns[i]='L';
ans+=dfs(i+1,ns);
ns[i]='_';
return ans;
}
int main()
{
yy['A']=yy['E']=yy['I']=yy['O']=yy['U']=1;
yy['_']=-1;
char chr[1001];
scanf("%s",chr);
cout<<dfs(0,chr);
return 0;
}
|
从 9 s 降到 30ms，质的提升啊！
哦。