• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            syhd142  
            日歷
            <2025年8月>
            272829303112
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456
            統計
            • 隨筆 - 23
            • 文章 - 122
            • 評論 - 31
            • 引用 - 0

            導航

            常用鏈接

            留言簿(2)

            隨筆檔案(23)

            文章分類(270)

            文章檔案(122)

            我的豆瓣

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

             
            據說經典DP,設opt[i][j]表示第二個基因序列的前i個基因和第一個基因序列的前j個匹配得到的最大值。
            那么可以得到轉移方程啊opt[i][j] = max(a[i-1][j-1]+table[b[i-1]][a[i- ]], opt[i-1][j]+table['-'][a[j]], opt[i][j-1]+table[b[i]]['-']);
            最后需要注意的就是邊界情況,即基因都匹配空的情況。
            #include <stdio.h>
            #include 
            <string.h>

            #define N 105
            #define MAX(a, b) (a > b ? a : b)

            int a[N][N];
            char s1[N], s2[N];

            int table[5][5= 
            {{
            5-1-2-1-3},
             {
            -15-3-2-4}, 
             {
            -2-35-2-2}, 
             {
            -1-2-25-1}, 
             {
            -3-4-2-10}};

            inline 
            int hash(char s)
            {
                
            if(s == 'A'return 0;
                
            if(s == 'C'return 1;
                
            if(s == 'G'return 2;
                
            if(s == 'T'return 3;
                
            if(s == '-'return 4;
            }

            int main()
            {
                
            int t, l1, l2;
                scanf(
            "%d"&t);
                
            while(t--)
                {
                    scanf(
            "%d %s"&l1, &s1);
                    scanf(
            "%d %s"&l2, &s2);
                    memset(a, 
            0sizeof(a));
                    
            for(int i = 0; i < l1; i++)
                    {
                        a[
            0][i + 1= a[0][i] + table[4][hash(s1[i])];
                    }
                    
            for(int i = 0; i < l2; i++)
                    {
                        a[i 
            + 1][0= a[i][0+ table[hash(s2[i])][4];
                    }
                    
            for(int i = 1; i <= l2; i++)
                    {
                        
            int x, y;
                        x 
            = hash(s2[i - 1]);
                        
            for(int j = 1; j <= l1; j++)
                        {
                            y 
            = hash(s1[j - 1]);
                            
            int t1, t2, t3;
                            t1 
            = a[i - 1][j - 1+ table[x][y];
                            t2 
            = a[i - 1][j] + table[x][4];
                            t3 
            = a[i][j - 1+ table[4][y];
                            a[i][j] 
            = MAX(t1, MAX(t2, t3));
                        }
                    }
                    printf(
            "%d\n", a[l2][l1]);
                }
                
            return 0;
            }
            posted on 2010-06-04 12:23 Fucker 閱讀(110) 評論(0)  編輯 收藏 引用 所屬分類: ACM/ICPCDP
             
            Copyright © Fucker Powered by: 博客園 模板提供:滬江博客
            99久久精品国产一区二区| 久久最近最新中文字幕大全| 久久人人爽人人人人爽AV| 色狠狠久久AV五月综合| 国产精品久久久99| 天天躁日日躁狠狠久久| 久久精品国产精品亜洲毛片| 久久久国产乱子伦精品作者| 国产高清国内精品福利99久久| 久久人人爽人人爽人人av东京热| AAA级久久久精品无码区| 亚洲国产精品无码久久久秋霞2| 久久久精品波多野结衣| 久久91精品国产91久久小草| 亚洲午夜久久久久久久久久| 久久人人爽人人爽人人片AV东京热| AV无码久久久久不卡蜜桃| 久久综合亚洲色HEZYO社区 | 久久不见久久见免费视频7| 久久91这里精品国产2020| AAA级久久久精品无码片| 亚洲综合熟女久久久30p| 一本综合久久国产二区| 蜜臀久久99精品久久久久久| 大香网伊人久久综合网2020| 久久久久久久尹人综合网亚洲| 亚洲AV无码久久精品色欲| 三级片免费观看久久| 无码任你躁久久久久久| 久久精品国产清自在天天线| 久久高清一级毛片| 久久99精品久久久久久齐齐| 国产三级观看久久| 久久激情五月丁香伊人| 久久精品国产WWW456C0M| 久久久久国产视频电影| 欧洲国产伦久久久久久久| 免费精品久久天干天干| 久久综合久久自在自线精品自| 久久精品九九亚洲精品| 久久婷婷国产麻豆91天堂|