hdu1080 Human Gene Functions (動态規劃)

http://acm.hdu.edu.cn/showproblem.php?pid=1080

難得徒手撸一題dp……

并不能是lcs，隻能是有點像

剛看到有點迷茫，比較自然地确定一個狀态dp[i][j]，表示處理到串a的i位，串b的j位

然而存在着一個’-‘的設定……

先假定為dp[i][j]指的結果的是對齊了的，有一方的結尾是’-‘或者都不是’-‘

對于一個狀态i,j來說，可以從i-1,j-1或者i,j-1或者i-1,j轉移而來。i-1和j-1就是讓ai和bj比對，i,j-1轉移則是讓ai和bj-1比對，多出來的bj和’-‘去比對，i-1,j同理。

dp[i][j]=max(dp[i-1][j-1]+add[i][j],dp[i-1][j]+add[A[i]][‘-‘],dp[i][j-1]+add[‘-‘][B[j]])

add表示兩個符号比對的評價。

錄入字元串的時候轉化為數字，這樣處理起來友善點。

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;
int add[][]=
{
    ,-,-,-,-,
    -,,-,-,-,
    -,-,,-,-,
    -,-,-,,-,
    -,-,-,-,-
};
int dp[][];
void process(char* start,int n)
{
    for (int i=;i<n;i++)
    {
        if (start[i]=='A')
            start[i]=;
        if (start[i]=='C')
            start[i]=;
        if (start[i]=='G')
            start[i]=;
        if (start[i]=='T')
            start[i]=;
    }
}
int main()
{
    char A[],B[];
    int ALen,BLen;
    int Total;
    cin.sync_with_stdio(false);
    cin>>Total;
    for (int C=;C<Total;C++)
    {
        cin>>ALen>>A+>>BLen>>B+;
        process(A+,ALen);
        process(B+,BLen);

        //注意初始化！[i][0]表示i個'-'和前i個字母對
        dp[][]=;
        for (int i=;i<=ALen;i++)
        {
            dp[i][]=add[A[i]][]+dp[i-][];
        }
        for (int i=;i<=BLen;i++)
        {
            dp[][i]=add[B[i]][]+dp[][i-];
        }
        for (int i=;i<=ALen;i++)
        {
            for (int j=;j<=BLen;j++)
            {
                int result(dp[i-][j-]+add[A[i]][B[j]]);
                result=max(result,dp[i-][j]+add[A[i]][]);
                result=max(result,dp[i][j-]+add[][B[j]]);
                dp[i][j]=result;
            }
        }
        cout<<dp[ALen][BLen]<<endl;
    }
    return ;
}