题目链接:点击打开链接
最长公共子序列。每一个字符都有一个权重。小小改一下就好。
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <map> using namespace std; const int N = 2005; int dp[N][N]; map<char, int> M; int lcs(char *s1, char *s2){ int len1 = strlen(s1), len2 = strlen(s2); memset(dp, 0, sizeof(dp)); for(int i = 1; i <= len1; i ++){ for(int j = 1; j <= len2; j ++) if(s1[i - 1] == s2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + M[s1[i - 1]]; else dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]); } return dp[len1][len2]; } int main(){ int n; while(~scanf("%d", &n)){ char c; int d; for(int i = 1; i <= n; i ++){ getchar(); scanf("%c %d", &c, &d); M[c] = d; } char str1[N], str2[N]; scanf("%s %s", str1, str2); printf("%d\n",lcs(str1, str2)); } return 0; }
最长公共子序列很的简单,但是很久都没有接触过dp了。还是需要全面的发展的。
dp[i][j] 代表第一个序列的前i个元素和第二个序列的前j个元素最长公共子序列。
如果第一个序列的第i个元素和第二个序列的第j个元素相同,那么dp[i][j] = dp[i - 1][j - 1] + 1,也就是说第一个序列的前i个元素和第二个序列的前j个元素的最长公共子序列为第一个序列的前i - 1个元素和第二个序列的前j - 1个元素的最长公共子序列+1。
如果不同,第一个序列的前i个元素和第二个序列的前j个元素的最长公共子序列为第一个序列的前i - 1个元素和第二个序列的前j个元素的最长公共子序列和第一个序列的前i个元素和第二个序列的前j - 1个元素的最长公共子序列中的较大者。为最优解。
那么对于这道题来说,只不过是对于每一个字符加了一个权重而已。每次增加的不在是1,而是相同字符的权重。
dp也要搞。慢慢来。