• <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>

            A Za, A Za, Fighting...

            堅信:勤能補拙

            PKU 1080 Human Gene Functions

            問題:
            http://acm.pku.edu.cn/JudgeOnline/problem?id=1080

            思路:
            想法與最長公共子序列類似
            用f[i][j]表示str_a[1..i]與str_b[1..j]的相似度,而所求即f[len_a][len_b],需要注意初始化部分的代碼
            狀態(tài)轉(zhuǎn)移方程見代碼注釋

            代碼:
             1 #include<stdio.h>
             2 #include<stdlib.h>
             3 #include<string.h>
             4 #define MAX_LEN 101
             5 #define INF 'I'
             6 #define Score(ch_a, ch_b) (score[map[ch_a-'A']][map[ch_b-'A']])
             7 int len_a, len_b;
             8 char str_a[MAX_LEN+1], str_b[MAX_LEN+1];
             9 int table[MAX_LEN][MAX_LEN];
            10 const int score[][5= {{5,-1,-2,-1,-3}, {-1,5,-3,-2,-4}, {-2,-3,5,-2,-2}, {-1,-2,-2,5,-1}, {-3,-4,-2,-1,-65535}};
            11                               /* A    C          G    I                               T */  
            12 const int map[] = {0,-1,1,-1,-1,-1,2,-1,4,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,3};
            13 
            14 /*
            15  * f[i][j] represent the similarity of str_a[1..i] and str_b[1..j], so:
            16  *    f[i][j] = max { f[i-1][j-1]+Score(str_a[i], str_b[j]), 
            17  *                    f[i-1][j] + Score(str_a[i], '-'),
            18  *                    f[i][j-1] + Score('-', str_b[j]) }
            19  */
            20 int
            21 dp()
            22 {
            23     int i, j, a, b, c, max;
            24     /* Attention: Initialization */
            25     table[0][0= 0;
            26     for(i=1; i<=len_a; i++)
            27         table[i][0= table[i-1][0+ Score(str_a[i], INF);
            28     for(j=1; j<=len_b; j++)
            29         table[0][j] = table[0][j-1+ Score(str_b[j], INF);
            30     
            31     for(i=1; i<=len_a; i++) {
            32         for(j=1; j<=len_b; j++) {
            33             a = table[i-1][j-1+ Score(str_a[i], str_b[j]);
            34             b = table[i-1][j] + Score(str_a[i], INF);
            35             c = table[i][j-1+ Score(INF, str_b[j]);
            36             max = a > b ? a : b;
            37             max = c > max ? c : max;
            38             table[i][j] = max;
            39         }
            40     }
            41     return table[len_a][len_b];
            42 }
            43 
            44 int
            45 main(int argc, char **argv)
            46 {
            47     int tests;
            48     scanf("%d"&tests);
            49     while(tests--) {
            50         scanf("%d %s"&len_a, str_a+1);
            51         scanf("%d %s"&len_b, str_b+1);
            52         printf("%d\n", dp());
            53     }
            54 }

            posted on 2010-08-13 14:07 simplyzhao 閱讀(127) 評論(0)  編輯 收藏 引用 所屬分類: C_動態(tài)規(guī)劃

            導航

            <2010年7月>
            27282930123
            45678910
            11121314151617
            18192021222324
            25262728293031
            1234567

            統(tǒng)計

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            99久久精品国产毛片| 久久精品视频一| 91精品国产9l久久久久| 91精品国产乱码久久久久久| 久久久久四虎国产精品| 99久久精品国产一区二区蜜芽| 久久精品国产欧美日韩| 久久精品国产2020| 精品一区二区久久久久久久网站| 久久国产V一级毛多内射| 久久99久久99精品免视看动漫| 人人狠狠综合久久亚洲婷婷| 日韩AV毛片精品久久久| 国产99精品久久| 久久九九兔免费精品6| 久久成人国产精品二三区| 欧美久久久久久| 999久久久国产精品| 久久久久免费看成人影片| 久久亚洲国产成人影院网站| 国产亚洲综合久久系列| 中文字幕无码av激情不卡久久| 好久久免费视频高清| 中文字幕人妻色偷偷久久| 精品久久久久久久久久中文字幕| 精品久久久久久无码专区| 久久青青色综合| 综合久久精品色| 老司机午夜网站国内精品久久久久久久久 | 99热都是精品久久久久久| 久久久久免费精品国产| 久久精品国产亚洲av瑜伽| 91秦先生久久久久久久| 国产精品久久一区二区三区| 久久99精品久久久久久hb无码 | 久久久久久毛片免费播放| 亚洲精品无码成人片久久| 国产精品久久久久久久app| 少妇无套内谢久久久久| 久久久精品国产Sm最大网站| 久久99精品久久久久久秒播|