POJ 1080 Human Gene Functions(dp)

제목: 일치하는 최대 값을 맞추기 위해 두 문자열을 지정합니다
요구 사항: 두 문자가 일치할 수도 있고, 한 문자가'-'와 일치할 수도 있습니다.
그러나'-'두 개가 일치할 수는 없습니다. 예를 들면 다음과 같습니다.
AGTGATG
GTTAG
이 두 문자열은
AGTGATG
-GTTA-G
그렇다고 볼 수도 있고.
AGTGAT-G
-GT--TAG
분석: 이것은 변형된 가장 긴 공공 서열로 가장 좋은 해석이다.
1. 문자 i-1과 j-1을 뽑을 때 dp[i][j]=dp[i-1][j-1]+a[s1[i-1][s2[j-1]]];2. 문자 i-1을 취하고 j-1을 취하지 않을 때 dp[i][j]=dp[i-1][j]+a[s1[i-1]['-'];3. 문자 j-1을 취하고 i-1을 취하지 않을 때 dp[i][j]=dp[i][j-1]+a['-'][s2[j-1]];
dp[i][j]는 이 세 개의 최대치를 취하면 됩니다.
물론 초기화할 때 dp[0][0]=0;그러나 모든 문자는 한 문자와 정렬해야 하기 때문에'-'와'-'두 문자를 포함하지 않기 때문에 dp[0][i]일 때 s2[i-1]와'-'가 정렬된다.
그래서 dp[0][j]=dp[0][j-1]+a['-'][s2[j-1]];같은 이치 dp[i][0]=dp[i-1][0]+a[s1[i-1]]['-'];

 1 #include
 2 char s1[110],s2[110];
 3 int dp[110][110];
 4 int n1,n2;
 5 int a[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};
 6 int max(int a,int b,int c)
 7 {
 8     int maxn=a;
 9     if(b>maxn)
10         maxn=b;
11     if(c>maxn)
12         maxn=c;
13     return maxn;
14 }
15 int get(char ch)
16 {
17     if(ch=='A')
18         return 0;
19     if(ch=='C')
20         return 1;
21     if(ch=='G')
22         return 2;
23     if(ch=='T')
24         return 3;
25     if(ch=='-')
26         return 4;
27 }
28 void dpdp()
29 {
30     dp[0][0]=0;
31     int x,y,z;
32     int i,j;
33     for(i=1; i<=n1; i++)
34         dp[i][0]=dp[i-1][0]+a[get(s1[i-1])][get('-')];
35     for(j=1; j<=n2; j++)
36         dp[0][j]=dp[0][j-1]+a[get('-')][get(s2[j-1])];
37     for(i=1; i<=n1; i++)
38     {
39         for(j=1; j<=n2; j++)
40         {
41             x=dp[i-1][j-1]+a[get(s1[i-1])][get(s2[j-1])];
42             y=dp[i-1][j]+a[get(s1[i-1])][get('-')];
43             z=dp[i][j-1]+a[get('-')][get(s2[j-1])];
44             dp[i][j]=max(x,y,z);
45         }
46     }
47     return ;
48 }
49 int main()
50 {
51     int t;
52     scanf("%d",&t);
53     while(t--)
54     {
55         scanf("%d%s%d%s",&n1,s1,&n2,s2);
56         dpdp();
57         printf("%d
",dp[n1][n2]);
58     }
59     return 0;
60 }