一组单词是安全的，当且仅当不存在一个单词是另一个单词的前缀，这样才能保证数据不容易被误解，现在你手上有一个单词集合S，你需要计算有多少个子集是安全的。
注意：空集永远是安全的。
【输入】
第一行一个数n，表示集合大小，以下n行，每行一个由‘a’..‘z’构成的字符串
【输出】
安全子集的个数
【样例输入】
3
hello
hell
hi
【样例输出】
6
数据规模
30%的数据满足： 1≤n≤10；
100%数据满足: 1≤n≤50
字符串长度≤50，没有两个字符串是完全相同的。
==========================================================================
一开始为了方便处理，想建立一棵TRIE树，但是算节点的时候算错了所以就没写了..TRIE树只需要50*50=2500个节点的，但是咱是以为没有用的地方都要建立，所以需要 26^50 个节点，这里肯定爆内存，所以说没有写TRIE树。标准做法是写TRIE树再做树型DP。不过咱还是直接叫递推了，首先，如果我们选择了某个点，那么它的子树下的单词就都不能选择了，那么我们假设只选择这个子树及该节点的方案总数，那么这个是与其他的树无关的，也就是说这是没有决策后效性的，于是我们设F[I]表示第i个节点以及其子树下的所有单词的方案数，那么设各个儿子为F[SI]，那么根据乘法原理的话，我们再把I这个节点加进去考虑的话，则为 TT（F[SI]）（不选择该节点，选择子树下的节点的）+1(只选择这个节点的） （注意假如这个节点上没有单词的话就不能加1了，这个可以用ORD(C[K])表示，当有单词的话标记为TRUE,其ASCII码值为1，否则为0），初始状态叶子节点均初始化为2即可。
另外上面的方法在计算DP的时候标程使用的是递归，这样就不需要考虑FOR循环的顺序，而且本题也往往写不出什么顺序来。这里的方法就是DFS深搜的时候顺便计算好，为O（N）的，N为所有字符串的总长度，插入也是这个复杂度，所以总的复杂度就是O(N)。
然后就是自己的思考了，既然它要我们不要把有前缀的放一起，我们就一开始求出所有的符合的前缀来。这个的复杂度就是2500即可，然后我们可以知道，对于一个字符串S，如果存在P1，P2都是它的前缀，那么很显然P1，P2也不能放在一起。也就是说，S,P1，P2中只能选择一个，这看起来就有点像强连通分量的感觉，我们一开始使用暴力求出每个字符串的前缀的P1，P2，PI,对它们使用并查集来维护，这样我们就求出了一系列的强连通分量，但是这个强连通分量里面是有可能有重复的节点的。对于每一个强连通分量，我们再新加一个节点0表示未在这个强连通分量中选择元素，这样子的话就可以根据乘法原理做了。答案为 TT(M[I]) (m[i]表示强连通分量中元素的个数），但是由于强连通分量中可能有重复的元素，所以这个方法并不是完全正确的，如果直接交上去经试验只有40分。但是我们可以把它分为没有联系的和有联系的，没联系的就是指不存在强连通分量的，这一部分直接乘法原理求。而有联系的部分我们可以使用枚举情况搜索的方法.....(CB同学的想法...他想的比咱的现实多了，咱实在太理想了....)，这样子做可以拿90分...当然为了精益求精咱们还必须继续努力，那么咱们可以试一试搜索并加一点剪枝，对于原字符串可以建图，对于P1是P2的前缀的时候我们就不在他们之间连边，对于其他的情况我们都可以连边，然后，同样可以使用递推之类的来求方案数，但是这可能很麻烦....
这里附一个咱写的TRIE树的AC程序
program prefix;
var t:array[1..2500,0..25]of longint;
c:array[1..2500]of boolean;
n,tot:longint;
s:string;
function dfs(p:longint):int64;
var i:longint;
ans:int64;
begin
ans:=1;
for i:=0 to 25 do
if t[p,i]<>0 then ans:=ans*dfs(t[p,i]);
exit(ans+ord(c[p]));
end;
procedure main;
var i,j:longint;
begin
write(dfs(1));
close(output);
end;
procedure insert(p:string);
var i,j,k,m:longint;
begin
j:=length(p);
i:=0;
k:=1;
while i<j do
begin
inc(i);
m:=ord(p[i])-ord('a');
if t[k,m]<>0 then k:=t[k,m]
else begin
inc(tot);
t[k,m]:=tot;
k:=tot;
end;
end;
c[k]:=true;
end;
procedure prepare;
var i,j:longint;
begin
for i:=1 to 2500 do
for j:=0 to 25 do
t[i,j]:=0;
fillchar(c,sizeof(c),false);
end;
procedure init;
var i:longint;
begin
assign(input,'prefix.in');
reset(input);
assign(output,'prefix.out');
rewrite(output);
readln(n);
tot:=1;
prepare;
for i:=1 to n do
begin
readln(s);
insert(s);
end;
end;
begin
init;
main;
end.
评论