題目描述

給出兩個(gè)基因串，你需要在其中插入任意個(gè)空格，使得兩個(gè)串長(zhǎng)度相同。如果兩個(gè)串的某同一位置都是字母則獲得某給定收益，對(duì)于每個(gè)串的每個(gè)長(zhǎng)度為k的連續(xù)空格段要付出a(k-1)+b的損失。求最大凈收益。

輸入

輸入第1行一個(gè)字符串，表示小A的DNA序列。 輸入第2行一個(gè)字符串，表示小B的DNA序列。 接下來(lái)4行，每行4個(gè)整數(shù)，用空格隔開，表示d數(shù)組， 具體順序如下所示。 d(A,A)d(A,T)d(A,G)d(A,C) d(T,A)d(T,T)d(T,G)d(T,C) d(G,A)d(G,T)d(G,G)d(G,C) d(C,A)d(C,T)d(C,G)d(C,C) 最后一行兩個(gè)用空格隔開的正整數(shù)A,B，意義如題中所述。 對(duì)于所有測(cè)試點(diǎn) 有0<B<A≤1000,-1000≤d(x,y)≤1000,d(x,y)=d(y,x)， 序列只包含{A,T,G,C}四種字符。 N+M<=3000

輸出

輸出共一行，表示兩個(gè)序列的最大相似程度

樣例輸入

ATGG
ATCC
5 -4 -4 -4
-4 5 -4 -4
-4 -4 5 -4
-4 -4 -4 5
2 1

樣例輸出

4

---

題解

dp

顯然空格匹配空格是血虧的，所以一定不會(huì)有兩個(gè)位置都是空格。

于是可以分別設(shè) $f[i][j],g[i][j],h[i][j]$ 表示第一個(gè)串匹配到 $i$ ，第二個(gè)串匹配到 $j$ ，最后為 空格&字母/字母&空格/字母&字母 的最大收益。

那么直接枚舉 $i$ 和 $j$ 轉(zhuǎn)移即可。

注意一下邊界問題。

時(shí)間復(fù)雜度 $O(nm)$?

#include <cstdio> #include <cstring> #include <algorithm> #define N 3010 #define val(c) (c == 'A' ? 0 : c == 'T' ? 1 : c == 'G' ? 2 : 3) using namespace std; int v[4][4] , f[N][N] , g[N][N] , h[N][N]; char A[N] , B[N]; int main() {int n , m , i , j , p , q;scanf("%s%s" , A + 1 , B + 1) , n = strlen(A + 1) , m = strlen(B + 1);for(i = 0 ; i < 4 ; i ++ )for(j = 0 ; j < 4 ; j ++ )scanf("%d" , &v[i][j]);scanf("%d%d" , &p , &q);memset(f , 0xc0 , sizeof(f));memset(g , 0xc0 , sizeof(g));memset(h , 0xc0 , sizeof(h));f[0][1] = g[1][0] = -p , h[0][0] = 0;for(i = 2 ; i <= m ; i ++ ) f[0][i] = f[0][i - 1] - q;for(i = 2 ; i <= n ; i ++ ) g[i][0] = g[i - 1][0] - q;for(i = 1 ; i <= n ; i ++ ){for(j = 1 ; j <= m ; j ++ ){f[i][j] = max(f[i][j - 1] - q , max(g[i][j - 1] , h[i][j - 1]) - p);g[i][j] = max(max(f[i - 1][j] , h[i - 1][j]) - p , g[i - 1][j] - q);h[i][j] = max(max(f[i - 1][j - 1] , g[i - 1][j - 1]) , h[i - 1][j - 1]) + v[val(A[i])][val(B[j])];}}printf("%d\n" , max(max(f[n][m] , g[n][m]) , h[n][m]));return 0; }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/GXZlegend/p/7992539.html

總結(jié)

以上是生活随笔為你收集整理的【bzoj5107】[CodePlus2017]找爸爸 dp的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。