gzwzm06

C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合

:: 管理 ::

1 隨筆 :: 52 文章 :: 17 評論 :: 0 Trackbacks

<

2025年11月

>

日

一

二

三

四

五

六

26

27

28

29

30

31

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1

2

3

4

5

6

常用鏈接

留言簿(3)

隨筆檔案

2009年5月 (1)

文章分類

文章檔案

搜索

最新評論

1.?re: Pku 2774--Long Long Message（后綴樹）
求教大牛，那個Lt屬性是記錄什么的
--dereky
2.?re: POJ 2481(樹狀數組)
@gzwzm06
哦，實在是不好意思，確實是那個地方，現在過了，謝謝了啊。
--Klion
3.?re: POJ 2481(樹狀數組)
你再檢查下，cc[j].m_e == cc[j].m_e這個條件肯定是真的，沒有意義吧
--gzwzm06
4.?re: POJ 2481(樹狀數組)
@gzwzm06
兩個相同一起比較也就是兩個區間是一樣的，起點和終點是相同的，和您的第80行比較的應該是一樣的吧？
--Klion
5.?re: POJ 2481(樹狀數組)
評論內容較長,點擊標題查看
--gzwzm06

Pku 1080--Human Gene Functions

#include <stdio.h>

const int Table[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

} ;

const int MAXN = 102 ;

int Ctoi( char &c )

{

switch( c )

{

case 'A':

return 0 ;

case 'C':

return 1 ;

case 'G':

return 2 ;

case 'T':

return 3 ;

}

return -1 ;

}

int main()

{

int N , m , n , i , j , Ftmp[MAXN] , Stmp[MAXN] ;

int mem[MAXN][MAXN] ;

char str1[MAXN], str2[MAXN] ;

scanf("%d", &N) ;

for ( i = 0 ; i < N ; ++i )

{

scanf("%d %s", &m, &str1) ;

scanf("%d %s", &n, &str2) ;

for ( j = 0 ; j < m ; ++j )

{

Ftmp[j + 1] = Ctoi( str1[j] ) ;

}

for ( j = 0 ; j < n ; ++j )

{

Stmp[j + 1] = Ctoi( str2[j] ) ;

}

mem[0][0] = 0 ;

for ( j = 1 ; j <= m ; ++j )

{

mem[j][0] = mem[j - 1][0]+ Table[4][Ftmp[j]] ;

}

for ( j = 1 ; j <= n ; ++j )

{

mem[0][j] = mem[0][j - 1] + Table[4][Stmp[j]] ;

}

int k ;

for ( j = 1 ; j <= m ; ++j )

for ( k = 1 ; k <= n ; ++k )

{

mem[j][k] = mem[j - 1][k - 1] + Table[Ftmp[j]][Stmp[k]] ;

if ( mem[j][k] < mem[j - 1][k] + Table[Ftmp[j]][4] )

mem[j][k] = mem[j - 1][k] + Table[Ftmp[j]][4] ;

if ( mem[j][k] < mem[j][k - 1] + Table[4][Stmp[k]] )

mem[j][k] = mem[j][k - 1] + Table[4][Stmp[k]] ;

}

printf("%d\n", mem[m][n]) ;

}