湘潭大学OJ 1171 DNA

现在的位置: 首页 > 综合 > 正文

湘潭大学OJ 1171 DNA

2017年11月17日 ⁄ 综合 ⁄ 共 2616字 ⁄ 字号小中大 ⁄ 评论关闭

湘潭市赛题目：DNA

DNA
Accepted : 23		Submit : 128
Time Limit : 25000 MS		Memory Limit : 65536 KB

Problem Description

GG stole a DNA single chain from the lab, now he plans to do something evil.
He takes up his favourite knife and plan to cut it into small fragments, and sell for money...
The store only accpet some particular fragment whose length is less than 100.
For example,
GG for 100
ACG for 50
GGAC for 10000
And GG as a DNA sequence GGCAGGTACGG,
The optimize way for him is cut it to GG(sell for 100), CAGG(sell for 10000), TAC(throw directly), GG(sell for 100)
So that, he got 10200 money.

Input

Multiply test cases. First line, an integer T ( 1 ≤ T ≤ 100 ), indicating the number of testcases.
For each test cases, Firstly comes a blank line. Then a number n ( 1 ≤ n ≤ 1000 ) in a line, indicating the kinds of fragment the store accept.
The following n lines, on each line there is a string si, and an integer wi ( 1 ≤ |si| ≤ 100, SIGMA = {A,T,G,C}, 1 ≤ wi ≤ 10000 ) indication one acceptable fragments and his value.
At last, there is a string s ( 1 ≤ |s| ≤ 100000 ), indication the DNA sequence GG plan to cut...

Ouput

For each test case, output an integer w, indicating the account of money GG can earn most by selling the framents of DNA.

Sample Input

1

3
GG 100
ACG 50
GGAC 10000
GGCAGGTACGG

Sample Output

解题思路：Tri树+DP

#include <cstdio>
#include <cstring>

using namespace std;

struct Tri{
    int key;
    struct Tri*next[5];
}Head_;

char CH[200],CH1[200],S[110000];
int d[110000];

int choose_(char ch)
{
    switch(ch)
    {
        case 'A':return 0;
        case 'C':return 1;
        case 'G':return 2;
        case 'T':return 3;
    }
}

void fun_insert(Tri*node,char *CH,int &num,int ff)
{
    int i;
    if(CH[ff]==0)
    {
        if(node==NULL)
        {
            node=new struct Tri;
            node->key=0;
            for(i=0;i<4;i++)
                node->next[i]=NULL;
        }
        if(num>node->key)
            node->key=num;
        return ;
    }
    if(node->next[choose_(CH[ff])]==NULL)
    {
        node->next[choose_(CH[ff])]=new struct Tri;
        node->next[choose_(CH[ff])]->key=0;
        for(i=0;i<4;i++)
            node->next[choose_(CH[ff])]->next[i]=NULL;
    }
    fun_insert(node->next[choose_(CH[ff])],CH,num,ff+1);
}

void fun_watch(Tri *node,char *S,int ff,int flag)
{
    if(node==NULL)
        return ;
    if(ff>0 && d[flag]+node->key>d[flag+ff])
        d[flag+ff]=d[flag]+node->key;
    if(S[ff]==0)
        return ;
    if(node->next[choose_(S[ff])]!=NULL)
        fun_watch(node->next[choose_(S[ff])],S,ff+1,flag);
}

void Dele(Tri *node)
{
    int i;
    for(i=0;i<4;i++)
    {
        if(node->next[i]!=NULL)
        {
            Dele(node->next[i]);
        }
        delete node->next[i];
    }
}

int main()
{
    int T,n;
    int i,j,len,num,tmp;
//    freopen("E:\\in.txt","r",stdin);
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        Head_.key=0;
        for(i=0;i<4;i++)
            Head_.next[i]=NULL;

        for(i=1;i<=n;i++)
        {
            scanf("%s %d",CH,&num);
            fun_insert(&Head_,CH,num,0);
            tmp=strlen(CH);
            for(j=0;j<tmp;j++)
                CH1[j]=CH[tmp-j-1];
            CH1[tmp]=0;
            fun_insert(&Head_,CH1,num,0);
        }
        scanf("%s",S);
        len=strlen(S);
        memset(d,0,(len+1)*sizeof(d[0]));
        for(i=1;i<=len;i++)
        {
            if(d[i]<d[i-1])
                d[i]=d[i-1];
            fun_watch(&Head_,S+i-1,0,i-1);
        }
 /*       for(i=0;i<=len;i++)
            printf("%d %d\n",i,d[i]);
*/
        printf("%d\n",d[len]);
        Dele(&Head_);
    }
    return 0;
}

【上篇】用Treap实现的名次树
【下篇】WINXP操作系统下如何重新安装TCPIP协议

作者: HollisMcgill

该日志由 HollisMcgill 于7年前发表在综合分类下，最后更新于 2017年11月17日.
转载请注明: 湘潭大学OJ 1171 DNA | 学步园 +复制链接

抱歉!评论已关闭.

学步园