标题效果：

举个很多种DNA弦，每个字符串值值至1。最后，一个长字符串。要安排你最后一次另一个字符串，使其没事子值和最大。

IDEAS：

首先easy我们的想法是想搜索的！管她3721。。直接一个字符一个字符的码，然后在AC自己主动机上推断最后的权值。TLE哟。

然后发现搜过不去。那就dp咯。再easy想到的就是dp[i][a][b][c][d] 表示此时遍历AC自己主动机的节点在i，然后构成了a个A，b个G，c个C。d个T的权值。

再一看内存，500*40*40*40*40...然后。。。就没有然后了

再想，由于它说的是这个串的长度是40。所以最多的状态就是10*10*10*10.。，所以开40^4就是浪费。所以要把状态hash下来。

关于hash ...cnt[0]-cnt[3] 表示ACGT的数量。  如今表示ABCD个ACGT  就是A*(cnt[3]+1)*(cnt[2]+1)*(cnt[1]+1)+B*(cnt[2]+1)*(cnt[1]+1)+C*(cnt[1]+1)+D*1

然后就依照上面的五维dp去做就好啦。

坑点就是。

。又有反复的串，人与人之间最主要的信任都没有。

#include <cstdio>

#include <iostream>

#include <cstring>

#include <algorithm>

#include <utility>

#define inf 0x3f3f3f3f

#include <vector>

using namespace std;

const char tab = 0;

const int max_next = 4;

int idx;

struct trie

{

    struct trie *fail;

    struct trie *next[max_next];

    int isword;

    int index;

};

int rev[256];

trie *que[100005],ac[100005];

int head,tail;

trie *New()

{

    trie *temp=&ac[idx];

    for(int i=0;i<max_next;i++)temp->next[i]=NULL;

    temp->fail=NULL;

    temp->isword=0;

    temp->index=idx++;

    return temp;

}

void Insert(trie *root,char *word,int len){

    trie *t=root;

    for(int i=0;i<len;i++){

        if(t->next[rev[word[i]]]==NULL)

            t->next[rev[word[i]]]=New();

        t=t->next[rev[word[i]]];

    }

    t->isword++;

}

void acbuild(trie *root){

    int head=0,tail=0;

    que[tail++]=root;

    root->fail=NULL;

    while(head<tail){

        trie *temp=que[head++],*p;

        for(int i=0;i<max_next;i++){

             if(temp->next[i]){

                if(temp==root)temp->next[i]->fail=root;

                else {

                    p=temp->fail;

                    while(p!=NULL){

                        if(p->next[i]){

                            temp->next[i]->fail=p->next[i];

                            break;

                        }

                        p=p->fail;

                    }

                    if(p==NULL)temp->next[i]->fail=root;

                }

                if(temp->next[i]->fail->isword)temp->next[i]->isword+=temp->next[i]->fail->isword;

                que[tail++]=temp->next[i];

             }

             else if(temp==root)temp->next[i]=root;

             else temp->next[i]=temp->fail->next[i];

        }

    }

}

void del()

{

    for(int i=0;i<idx;i++)

        free(&ac[i]);

}

void tra()

{

    for(int i=0;i<idx;i++)

    {

        if(ac[i].fail!=NULL)printf("fail = %d ",ac[i].fail->index);

        for(int k=0;k<max_next;k++)

            printf("%d ",ac[i].next[k]->index);

        puts("");

    }

}

char word[50];

int cnt[5];

int dp[515][11*11*11*11+5];

int bit[5];

int solve()

{

    memset(dp,-1,sizeof dp);

    dp[0][0]=0;

    bit[0]=(cnt[1]+1)*(cnt[2]+1)*(cnt[3]+1);

    bit[1]=(cnt[2]+1)*(cnt[3]+1);

    bit[2]=(cnt[3]+1);

    bit[3]=1;

    for(int A=0;A<=cnt[0];A++)

    {

        for(int B=0;B<=cnt[1];B++)

        {

            for(int C=0;C<=cnt[2];C++)

            {

                for(int D=0;D<=cnt[3];D++)

                {

                    int state=A*bit[0]+B*bit[1]+C*bit[2]+D*bit[3];

                    for(int i=0;i<idx;i++)

                    {

                        if(dp[i][state]>=0)

                        {

                            for(int k=0;k<4;k++)

                            {

                                if(k==0 && A==cnt[0])continue;

                                if(k==1 && B==cnt[1])continue;

                                if(k==2 && C==cnt[2])continue;

                                if(k==3 && D==cnt[3])continue;

                                dp[ac[i].next[k]->index][state+bit[k]]=max(dp[ac[i].next[k]->index][state+bit[k]],dp[i][state]+ac[i].next[k]->isword);

                            }

                        }

                    }

                }

            }

        }

    }

    int ans=0;

    int tag=cnt[0]*bit[0]+cnt[1]*bit[1]+cnt[2]*bit[2]+cnt[3]*bit[3];

    for(int i=0;i<idx;i++)

        ans=max(ans,dp[i][tag]);

    return ans;

}

int main()

{

    rev['A']=0;

    rev['C']=1;

    rev['G']=2;

    rev['T']=3;

    int n,cas=1;

    while(scanf("%d",&n)!=EOF && n)

    {

        idx=0;

        trie *root = New();

        for(int i=1;i<=n;i++)

        {

            scanf("%s",word);

            Insert(root,word,strlen(word));

        }

        acbuild(root);

        scanf("%s",word);

        int len=strlen(word);

        memset(cnt,0,sizeof cnt);

        for(int j=0;j<len;j++)

            cnt[rev[word[j]]]++;

        printf("Case %d: %d\n",cas++,solve());

    }

    return 0;

}