题目链接
题目描述很简单 有n和DNA序列，求出他们中公共前缀长度和有相同公共前缀DNA序列乘积的最大值。
If we take the subset {ACGT} then the result is 4 (4 * 1), if we take {ACGT, ACGTGCGT, ACGCCGT} then the result is 3 * 3 = 9 (since ACG is the common prefix), if we take {ACGT, ACGTGCGT, ACCGTGC, ACGCCGT} then the result is 2 * 4 = 8.
这个就是英文的描述，很简单，就不翻译了。
思路：
这个题目明显用trie做，我是这样想的，用trie存储所有的DNA序列，然后每个节点有个cnt值，表示的是存储以该节点结尾的DNA序列的数目。
在输入过程中便开始建树的过程，最后，在查询结果的时候我用了递归的方式，代码比较好写，也容易理解。
还有最后一点，虽然我们在竞赛中很少使用指针，但涉及到指针，在用完后一定要释放，否则会MLE，我就MLE两次。
代码：
代码语言：javascript复制#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct trie
{
struct trie *next[5];
int cnt;
} *p;
trie* newtrie()
{
trie *q = new trie();
for (int i = 0; i < 4; i )
q->next[i] = NULL;
q->cnt = 0;
return q;
};
void insert(char *str, trie *root)
{
p = root;
while (*str)
{
int pos;
if (*str == 'A')
pos = 0;
else if (*str == 'C')
pos = 1;
else if (*str == 'G')
pos = 2;
else
pos = 3;
if (!p->next[pos])
{
p->next[pos] = newtrie();
p = p->next[pos];
p->cnt ;
}
else
{
p = p->next[pos];
p->cnt ;
}
str ;
}
}
int maxnum(struct trie *q, int d)
{
int maxn = d * q->cnt;
for (int i = 0; i < 4; i )
{
if (q->next[i])
{
maxn = max(maxn, maxnum(q->next[i], d 1));
}
}
return maxn;
}
void moveit(trie *root)
{
if (root == NULL)
return;
for (int i = 0; i < 4;i )
{
moveit(root->next[i]);
}
free(root);
}
int main()
{
int t, n;
char s[55];
scanf("%d",&t);
for(int k = 1; k <= t; k )
{
trie *root = newtrie();
scanf("%d",&n);
while (n--)
{
scanf("%s",s);
insert(s, root);
}
printf("Case %d: %dn", k, maxnum(root, 0));
moveit(root);
}
return 0;
}
