• <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>
            posts - 100,  comments - 15,  trackbacks - 0
            第一題完全靠自己的DP,一遍AC高興...

             1#include<iostream>
             2using namespace std;
             3#define MAX 100
             4
             5int table['T'+1]['T'+1];    //scoring matrix
             6int score[MAX+1][MAX+1];    //score[i][j]表示a串有i個(gè)基,b串j個(gè)基的最大score
             7char a[MAX+1];  //string a
             8char b[MAX+1];  //string b
             9int la;  //length of a
            10int lb;  //length of b
            11
            12void init()
            13{
            14    table['A']['A']=5;
            15    table['A']['C']=-1;
            16    table['A']['G']=-2;
            17    table['A']['T']=-1;
            18    table['A']['-']=-3;
            19
            20    table['C']['A']=-1;
            21    table['C']['C']=5;
            22    table['C']['G']=-3;
            23    table['C']['T']=-2;
            24    table['C']['-']=-4;
            25
            26    table['G']['A']=-2;
            27    table['G']['C']=-3;
            28    table['G']['G']=5;
            29    table['G']['T']=-2;
            30    table['G']['-']=-2
            31        ;
            32    table['T']['A']=-1;
            33    table['T']['C']=-2;
            34    table['T']['G']=-2;
            35    table['T']['T']=5;
            36    table['T']['-']=-1;
            37
            38    table['-']['A']=-3;
            39    table['-']['C']=-4;
            40    table['-']['G']=-2;
            41    table['-']['T']=-1;
            42}

            43void dp()
            44{
            45    int i,j;
            46    score[0][0]=0;
            47    for(i=1;i<=la;i++)
            48        score[i][0]=score[i-1][0]+table[a[i]]['-'];
            49    for(i=1;i<=lb;i++)
            50        score[0][i]=score[0][i-1]+table['-'][b[i]];
            51    for(i=1;i<=la;i++)
            52        for(j=1;j<=lb;j++)
            53            score[i][j]=max(score[i-1][j-1]+table[a[i]][b[j]],max(score[i][j-1]+table['-'][b[j]],score[i-1][j]+table[a[i]]['-']));
            54}

            55
            56
            57int main()
            58{
            59    int T;
            60    scanf("%d",&T);
            61    init();
            62    while(T--)
            63    {
            64        memset(a,0,sizeof(a));
            65        memset(b,0,sizeof(b));
            66        scanf("%d",&la);
            67        scanf("%s",a+1);
            68        scanf("%d",&lb);
            69        scanf("%s",b+1);
            70        dp();
            71        printf("%d\n",score[la][lb]);
            72    }

            73    return 0;
            74}

            75

            posted on 2009-05-02 16:21 wyiu 閱讀(220) 評(píng)論(0)  編輯 收藏 引用 所屬分類: POJ
            久久婷婷五月综合成人D啪| 久久久久四虎国产精品| 欧美国产成人久久精品| 欧美激情精品久久久久久久| 综合久久精品色| 国内精品人妻无码久久久影院导航 | 亚洲欧美精品伊人久久| 国产福利电影一区二区三区久久老子无码午夜伦不 | 久久国产综合精品五月天| 亚洲国产精品成人久久蜜臀 | 99久久精品国产高清一区二区| 久久久国产精品网站| 亚洲综合久久久| 久久精品国产亚洲av日韩| 久久精品18| 99久久综合狠狠综合久久止| 尹人香蕉久久99天天拍| 91精品国产色综久久 | 狠狠色丁香久久婷婷综合_中 | 亚洲国产精品久久66| 国产精品美女久久福利网站| 中文精品久久久久国产网址| 一本色道久久综合狠狠躁| 国产免费福利体检区久久| 7777久久亚洲中文字幕| 伊人久久综合精品无码AV专区| 亚洲成av人片不卡无码久久| 久久综合狠狠综合久久激情 | 亚洲国产欧洲综合997久久| 国内精品久久久久影院亚洲| 国产精品免费久久| 国产精品成人99久久久久91gav| 国产精品9999久久久久| 麻豆亚洲AV永久无码精品久久| 欧美久久久久久| 无码八A片人妻少妇久久| 久久综合亚洲色HEZYO社区| 欧美精品九九99久久在观看| 狠狠色丁香久久婷婷综合图片| 一本一道久久a久久精品综合| 欧美久久综合九色综合|