|
问题描述: 给出两个串,对应字母有权值,可以错位安排,使得最后总权和最大。 解题思路: 首先定义: rt[a][b] 表示字符a和字符b配对时的权值 dp[i][j] 表示第一个串到i和第二个串到j两个子串所组合出的最大权和为dp[i][j]; 1)如果第i个字符和第j个字符配对,那么dp[i][j] = dp[i-1][j-1] + rt[str1[i]][str2[j]]; 2)如果第一个串的第i个字符和'-'配对, 那么dp[i][j] = dp[i-1][j] + rt[str1[i]]['-']; 3)如果第二个串的第j个字符和'-'配对,那么dp[i][j] = dp[i][j-1] + rt['-'][str2[j]]; 于是dp[i][j] = max{ dp[i-1][j-1] + rt[str1[i]][str2[j]], dp[i-1][j] + rt[str1[i]]['-'], dp[i][j-1] + rt['-'][str2[j]] }; 核心代码: #include <iostream>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int dp[110][110];
char str[2][110];
int len[2];
int i, j;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int rt[5][5] = {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {5, -1, -2, -1, -3},
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {-1, 5, -3, -2, -4},
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {-2, -3, 5, -2, -2},
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {-1, -2, -2, 5, -1},
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {-3, -4, -2, -1, 0}
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int num(char c) {
if(c == 'A')
return 0;
if(c == 'C')
return 1;
if(c == 'G')
return 2;
if(c == 'T')
return 3;
return 4;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int Max(int a, int b, int c) {
if(c > b) b = c;
return a > b ? a : b;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int t;
scanf("%d", &t);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(t--) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = 0; i < 2; i++) {
scanf("%d", &len[i]);
scanf("%s", &str[i][1]);
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
dp[0][0] = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = 1; i <= len[0]; i++) {
dp[i][0] = dp[i-1][0] + rt[ num(str[0][i]) ][num('-')];
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = 1; i <= len[1]; i++) {
dp[0][i] = dp[0][i-1] + rt[ num('-') ][ num(str[1][i]) ];
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = 1; i <= len[0]; i++) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(j = 1; j <= len[1]; j++) {
dp[i][j] = Max(
dp[i-1][j-1] + rt[ num(str[0][i]) ][num(str[1][j])],
dp[i-1][j] + rt[ num(str[0][i]) ][ num('-') ],
dp[i][j-1] + rt[ num('-') ][ num(str[1][j]) ]
);
}
}
printf("%d\n", dp[ len[0] ][ len[1] ]);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
|