• <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個基,b串j個基的最大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) 評論(0)  編輯 收藏 引用 所屬分類: POJ
            漂亮人妻被黑人久久精品| 国产69精品久久久久观看软件| 久久久国产视频| 国产国产成人精品久久| 蜜臀久久99精品久久久久久| 亚洲AV日韩精品久久久久久久| 精品免费久久久久国产一区| 久久精品欧美日韩精品| 一本久久精品一区二区| 久久激情五月丁香伊人| 久久久久综合网久久| 久久丫精品国产亚洲av不卡| 91久久精品国产91性色也| 韩国无遮挡三级久久| 亚洲av伊人久久综合密臀性色| 久久精品免费观看| 久久精品国产乱子伦| 2021国产精品午夜久久| 久久久久综合网久久| 亚洲中文字幕久久精品无码喷水| 人人狠狠综合久久亚洲高清| 亚洲精品高清久久| 久久久久久久亚洲Av无码| 午夜精品久久久久久影视riav| 久久夜色精品国产亚洲| 亚洲国产精品无码久久| 久久久久久精品成人免费图片| 国产精品免费看久久久香蕉| 成人国内精品久久久久影院VR| 久久午夜伦鲁片免费无码| 中文字幕无码精品亚洲资源网久久| 草草久久久无码国产专区| www.久久热| 国内精品久久久久伊人av| 国产精品99久久久久久人| 狠狠色狠狠色综合久久| 伊人久久大香线蕉精品不卡 | 77777亚洲午夜久久多喷| 久久亚洲国产精品五月天婷| 国产午夜精品理论片久久| 国产精品免费久久久久久久久|