题目链接
题目描述很简单 有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两次。
代码：
#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: %d\n", k, maxnum(root, 0)); moveit(root); } return 0; }
