HDU 1080 POJ 1080 Human Gene Functions——动态规划

Posted on | In | Comments:
| 26k | 23 mins.

http://poj.org/problem?id=1080
http://acm.hdu.edu.cn/showproblem.php?pid=1080

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <iostream>
#include <cstdio>
#include <map>
#include <cstring>

#define MAX(x,y,z) ((x)>(y)?((x)>(z)?(x):(z)):((y)>(z)?(y):(z)))

using namespace std;

char str1[105];
char str2[105];
int list[6][6] = {
//	  		{ \0,  A,  C,  G,  T,  -}
	/*\0*/	{  0,  0,  0,  0,  0,  0},
	/*A*/	{  0,  5, -1, -2, -1, -3},
	/*C*/	{  0, -1,  5, -3, -2, -4},
	/*G*/	{  0, -2, -3,  5, -2, -2},
	/*T*/	{  0, -1, -2, -2,  5, -1},
	/*-*/	{  0, -3, -4, -2, -1,  0},
};
map<char, int>m;

int dp[105][105];//dp[x][y]表示str1中1...x-1个字符和str2中第1...y-1之间匹配的最优解

int main(int argc, char const *argv[])
{
	int T, len1, len2;
	scanf("%d", &T);

	m['\0'] = 0;
	m['A'] = 1;
	m['C'] = 2;
	m['G'] = 3;
	m['T'] = 4;
	m['-'] = 5;

	while (T--) {
		memset(dp, 0, sizeof(dp));
		scanf("%d%s", &len1, str1 + 1);
		scanf("%d%s", &len2, str2 + 1);

		// printf("\t\t");
		// for (int y = 0; y < len2; y++) {
		// 	printf("%c\t", s2[y]);
		// }
		// printf("\n\t");

		// for (int y = 0; y <= len2; y++) {
		// 	printf("%d\t", dp[0][y]);

		// }
		// printf("\n");

		for (int x = 1; x <= len1 + 1; x++) {
			dp[x][0] = -1e9;
		}

		for (int y = 1; y <= len2 + 1; y++) {
			dp[0][y] = -1e9;
		}

		for (int x = 1; x <= len1 + 1; x++) {

			for (int y = 1; y <= len2 + 1; y++) {
				dp[x][y] = MAX(
				               dp[x - 1][y - 1] + list[m[str1[x - 1]]][m[str2[y - 1]]],
				               dp[x - 1][y] + list[m[str1[x - 1]]][m['-']],
				               dp[x][y - 1] + list[m['-']][m[str2[y - 1]]]
				           );

//取消注釋打印流程

/*				if (dp[x - 1][y - 1] + list[m[str1[x - 1]]][m[str2[y - 1]]]
				        >= dp[x - 1][y] + list[m[str1[x - 1]]][m['-']]) {
					if (dp[x - 1][y - 1] + list[m[str1[x - 1]]][m[str2[y - 1]]]
					        >=
					        dp[x][y - 1] + list[m['-']][m[str2[y - 1]]]) {
						printf("↖%d\t", dp[x][y]);
					} else {
						printf("←%d\t", dp[x][y]);
					}
				} else {
					if (dp[x - 1][y] + list[m[str1[x - 1]]][m['-']]
					        >=
					        dp[x][y - 1] + list[m['-']][m[str2[y - 1]]]) {
						printf("↑%d\t", dp[x][y]);
					} else {
						printf("←%d\t", dp[x][y]);

					}
				}
*/

			}

/*
			printf("\n");
*/

		}
		printf("%d\n", dp[len1 + 1][len2 + 1]);

		/**
		*
		*	in:
		*	
		*	2
		*	7 AGTGATG
		*	5 GTTAG
		*	7 AGCTATT
		*	9 AGCTTTAAA
		*	
		*	out:
		*	
		*	↖0		←-2		←-3		←-4		←-7		←-9
		*	↑-3		↖-2		↖-3		↖-4		↖1		←-1
		*	↑-5		↖2		←1		←0		↑-1		↖6
		*	↑-6		↑1		↖7		↖6		←3		↑5
		*	↑-8		↖-1		↑5		↖5		↖4		↖8
		*	↑-11	↑-4		↑2		↖4		↖10		←8
		*	↑-12	↑-5		↖1		↖7		↑9		↖8
		*	↑-14	↖-7		↑-1		↑5		↑7		↖14
		*	
		*	14
		*	
		*	↖0		←-3		←-5		←-9		←-10	←-11	←-12	←-15	←-18	←-21
		*	↑-3		↖5		←3		←-1		←-2		←-3		←-4		↖-7		↖-10	↖-13
		*	↑-5		↑3		↖10		←6		←5		←4		←3		←0		←-3		←-6
		*	↑-9		↑-1		↑6		↖15		←14		←13		←12		←9		←6		←3
		*	↑-10	↑-2		↑5		↑14		↖20		↖19		↖18		←15		←12		←9
		*	↑-13	↖-5		↑2		↑11		↑17		↖19		↖18		↖23		↖20		↖17
		*	↑-14	↑-6		↑1		↑10		↖16		↖22		↖24		↑22		↖22		↖19
		*	↑-15	↑-7		↑0		↑9		↖15		↖21		↖27		←24		↖21		↖21
		*	
		*	
		*	21
		*	
		*	
		*	
		*/

	}
	return 0;
}

后来发现是自己想得太多了，这个题的“状态”不一定非要理解成原先那样，
其实完全可以也像最大公共子列那样的，
dp[x][y]表示str1的前x个字符和str2的前y个字符之间的匹配结果的最优解
这样也便于理解，便于思考

这样的话dp[x][y]就是最终答案，不过要注意边界的预处理
代码如下

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <iostream>
#include <cstdio>
#include <map>
#include <cstring>

#define MAX(x,y,z) ((x)>(y)?((x)>(z)?(x):(z)):((y)>(z)?(y):(z)))

using namespace std;

char str1[105];
char str2[105];
int list[6][6] = {
//	  		{  A,  C,  G,  T,  -}
	/*A*/	{  5, -1, -2, -1, -3},
	/*C*/	{ -1,  5, -3, -2, -4},
	/*G*/	{ -2, -3,  5, -2, -2},
	/*T*/	{ -1, -2, -2,  5, -1},
	/*-*/	{ -3, -4, -2, -1,  0},
};

map<char, int>m;

int dp[105][105];//dp[x][y]表示str1中1...x个字符和str2中第1...y这两个子串之间的所有匹配方式的最大利益

int main(int argc, char const *argv[])
{
	int T, len1, len2;
	scanf("%d", &T);

	m['A'] = 0;
	m['C'] = 1;
	m['G'] = 2;
	m['T'] = 3;
	m['-'] = 4;

	while (T--) {
		memset(dp, 0, sizeof(dp));
		scanf("%d%s", &len1, str1 + 1);
		scanf("%d%s", &len2, str2 + 1);

		// printf("\t\t");
		// for (int y = 0; y < len2; y++) {
		// 	printf("%c\t", s2[y]);
		// }
		// printf("\n\t");

		// for (int y = 0; y <= len2; y++) {
		// 	printf("%d\t", dp[0][y]);

		// }
		// printf("\n");

		for (int x = 1; x <= len1; x++) {
			dp[x][0] = dp[x - 1][0] + list[m[str1[x]]][m['-']];
		}

		// printf("↖0\t");
		for (int y = 1; y <= len2; y++) {
			dp[0][y] = dp[0][y - 1] + list[m[str2[y]]][m['-']];
			// printf("←%d\t", dp[0][y]);
		}
		// printf("\n");

		for (int x = 1; x <= len1; x++) {

			// printf("↑%d\t", dp[x][0]);

			for (int y = 1; y <= len2; y++) {
				dp[x][y] = MAX(
				               dp[x - 1][y - 1] + list[m[str1[x]]][m[str2[y]]],
				               dp[x - 1][y] + list[m[str1[x]]][m['-']],
				               dp[x][y - 1] + list[m['-']][m[str2[y]]]
				           );

//取消所有额外注释可打印流程
				/*
								if (dp[x - 1][y - 1] + list[m[str1[x]]][m[str2[y]]]
								        >= dp[x - 1][y] + list[m[str1[x]]][m['-']]) {
									if (dp[x - 1][y - 1] + list[m[str1[x]]][m[str2[y]]]
									        >=
									        dp[x][y - 1] + list[m['-']][m[str2[y]]]) {
										printf("↖%d\t", dp[x][y]);
									} else {
										printf("←%d\t", dp[x][y]);
									}
								} else {
									if (dp[x - 1][y] + list[m[str1[x]]][m['-']]
									        >=
									        dp[x][y - 1] + list[m['-']][m[str2[y]]]) {
										printf("↑%d\t", dp[x][y]);
									} else {
										printf("←%d\t", dp[x][y]);

									}
								}
				*/

			}

			/*
						printf("\n");
			*/

		}
		printf("%d\n", dp[len1][len2]);

		/**
		*
		*	in:
		*
		*	2
		*	7 AGTGATG
		*	5 GTTAG
		*	7 AGCTATT
		*	9 AGCTTTAAA
		*
		*	out:
		*
		*	↖0		←-2		←-3		←-4		←-7		←-9
		*	↑-3		↖-2		↖-3		↖-4		↖1		←-1
		*	↑-5		↖2		←1		←0		↑-1		↖6
		*	↑-6		↑1		↖7		↖6		←3		↑5
		*	↑-8		↖-1		↑5		↖5		↖4		↖8
		*	↑-11	↑-4		↑2		↖4		↖10		←8
		*	↑-12	↑-5		↖1		↖7		↑9		↖8
		*	↑-14	↖-7		↑-1		↑5		↑7		↖14
		*
		*	14
		*
		*	↖0		←-3		←-5		←-9		←-10	←-11	←-12	←-15	←-18	←-21
		*	↑-3		↖5		←3		←-1		←-2		←-3		←-4		↖-7		↖-10	↖-13
		*	↑-5		↑3		↖10		←6		←5		←4		←3		←0		←-3		←-6
		*	↑-9		↑-1		↑6		↖15		←14		←13		←12		←9		←6		←3
		*	↑-10	↑-2		↑5		↑14		↖20		↖19		↖18		←15		←12		←9
		*	↑-13	↖-5		↑2		↑11		↑17		↖19		↖18		↖23		↖20		↖17
		*	↑-14	↑-6		↑1		↑10		↖16		↖22		↖24		↑22		↖22		↖19
		*	↑-15	↑-7		↑0		↑9		↖15		↖21		↖27		←24		↖21		↖21
		*
		*
		*	21
		*
		*
		*
		*/

	}
	return 0;
}