P1140 相似基因

題目地址

這是一道DP的題目 搜索肯定解決不了 只能DP
DP的麻煩在于 如何確定狀態(tài)
如何列出狀態(tài)轉移方程

score[i][j]代表每個對應分數(shù)
input1 input2表示2列基因字母n和m是長度
dp[i][j]表示input2的第i個字母 對應input1 j-1字母所得的分數(shù)
j為0的時候代表 對應空字母

對于input2的第一個點 對面有n+1種情況
即對應對應空 或者對應input的0到n-1位置
j=0時
dp[0][0]=score[input2[0]][4];
j>0時
dp[0][j]=sum(score[4][0.....j-2])+score[input2[0]][input1[j-1]]

狀態(tài)轉移方程
有2種情況
如果input2的第i-1點對應的是input1 j-1點 那么第i個點只能對應空
value=dp[i-1][j]+score[input2[i]][4];
如果input2的第i-1點對應的是input1 0到j-2直接的數(shù)或者對應空
那么第i個點對應input1的j-1點
value=dp[i-1][k]+sum(score[4][k.....j-2])+score[input2[i]][input1[j-1]]
k from 0 to j-1
最后取最大值得到dp[i][j]

最后處理下input1未對應的點
然后取最后一行的最大值 就是結果

#include <stdio.h>

int getIndex(char c){
    switch (c)
    {
    case 'C':
        return 1;
    case 'G':
        return 2;
    case 'T':
        return 3;
    case 'A':
        return 0;
    default:
        return -1;
    }
}

const int MaxLen=200;

int* getInputArray(int n,char input[MaxLen])
{
    char c;
    int i=0,j=0;
    int* input1=new int[n];
    do
    {
        c=input[i];
        int index=getIndex(c);
        if(index>=0)
        {
            input1[j]=index;
            j++;
        }
        i++;
    }while (c!='\0'&&j<n);
   
    
    return input1;
}

void printArray(int** dp,int m,int n)
{
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            printf("%d\t",dp[i][j]);
        }
        printf("\n");
    }
}


int main(){
    int n,m;
    //每個對應關系的得分
    int score[5][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,0}};
    int i,j,k;

    char input[MaxLen];
    
    scanf("%d %s",&n,input);
    int* input1=getInputArray(n,input);

    scanf("%d %s",&m,input);
    int* input2=getInputArray(m,input);


    int n1=n+1;
    int m1=m+1;
    int** dp=new int*[m1];
    for(i=0;i<m1;i++)
    {
        dp[i]=new int[n1];
    }

    int* sumScore=new int[n1];
    sumScore[0]=0;
    //sumScore[i] input1 0到i-1元素對應空的時候的和
    for(i=1;i<n1;i++)
    {
        sumScore[i]=sumScore[i-1]+score[4][input1[i-1]];
    }

    
    //計算第0行的值
    dp[0][0]=score[input2[0]][4];
    for(i=1;i<n1;i++)
    {
        dp[0][i]=sumScore[i-1]+score[input2[0]][input1[i-1]];
    }
    for(i=1;i<m;i++)
    {
        for(j=0;j<n1;j++)
        {
            //i-1對應j-1的情況
            int max=dp[i-1][j]+score[input2[i]][4];
            for(k=0;k<j;k++)
            {
                //i-1對應k的情況
                int value=dp[i-1][k]+sumScore[j-1]-sumScore[k]+score[input2[i]][input1[j-1]];
                if(value>max)
                {
                    max=value;
                }
            }
            dp[i][j]=max;
        }
    }
    
    
    int max=-(m+n)*5;
    //處理input1 剩下未對應的點 計算出最終結果
    for(i=0;i<n1;i++)
    {
        dp[m][i]=dp[m-1][i]+sumScore[n]-sumScore[i];
        if(max<dp[m][i])
        {
            max=dp[m][i];
        }
    }

    // printArray(dp,m1,n1);

    delete input1;
    delete input2;
    delete sumScore;
    for(i=0;i<m1;i++)
    {
        delete dp[i];
    }
    delete dp;

    printf("%d\n",max);
    return 0;
}
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市框冀,隨后出現(xiàn)的幾起案子翎迁,更是在濱河造成了極大的恐慌巡蘸,老刑警劉巖咐蚯,帶你破解...
    沈念sama閱讀 222,681評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件健无,死亡現(xiàn)場離奇詭異,居然都是意外死亡火惊,警方通過查閱死者的電腦和手機求类,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評論 3 399
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來矗晃,“玉大人仑嗅,你說我怎么就攤上這事≌胖ⅲ” “怎么了仓技?”我有些...
    開封第一講書人閱讀 169,421評論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長俗他。 經常有香客問我脖捻,道長,這世上最難降的妖魔是什么兆衅? 我笑而不...
    開封第一講書人閱讀 60,114評論 1 300
  • 正文 為了忘掉前任地沮,我火速辦了婚禮,結果婚禮上羡亩,老公的妹妹穿的比我還像新娘摩疑。我一直安慰自己,他們只是感情好畏铆,可當我...
    茶點故事閱讀 69,116評論 6 398
  • 文/花漫 我一把揭開白布雷袋。 她就那樣靜靜地躺著,像睡著了一般辞居。 火紅的嫁衣襯著肌膚如雪楷怒。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,713評論 1 312
  • 那天瓦灶,我揣著相機與錄音鸠删,去河邊找鬼。 笑死贼陶,一個胖子當著我的面吹牛刃泡,可吹牛的內容都是我干的。 我是一名探鬼主播每界,決...
    沈念sama閱讀 41,170評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼捅僵,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了眨层?” 一聲冷哼從身側響起庙楚,我...
    開封第一講書人閱讀 40,116評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎趴樱,沒想到半個月后馒闷,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體酪捡,經...
    沈念sama閱讀 46,651評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 38,714評論 3 342
  • 正文 我和宋清朗相戀三年纳账,在試婚紗的時候發(fā)現(xiàn)自己被綠了逛薇。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 40,865評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡疏虫,死狀恐怖永罚,靈堂內的尸體忽然破棺而出,到底是詐尸還是另有隱情卧秘,我是刑警寧澤呢袱,帶...
    沈念sama閱讀 36,527評論 5 351
  • 正文 年R本政府宣布,位于F島的核電站翅敌,受9級特大地震影響羞福,放射性物質發(fā)生泄漏。R本人自食惡果不足惜蚯涮,卻給世界環(huán)境...
    茶點故事閱讀 42,211評論 3 336
  • 文/蒙蒙 一治专、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧遭顶,春花似錦张峰、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,699評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至嗦哆,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間婿滓,已是汗流浹背老速。 一陣腳步聲響...
    開封第一講書人閱讀 33,814評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留凸主,地道東北人橘券。 一個月前我還...
    沈念sama閱讀 49,299評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像卿吐,于是被迫代替她去往敵國和親旁舰。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 45,870評論 2 361

推薦閱讀更多精彩內容