UVA 1625 Color Length——dp

UVA 1625 Color Length——dp

类似于LCS的递推方法，状态的定义和转移包括辅助数组都不难想， 但是细节很多，比如说一个字符的开始和终止要综合考虑两个串，以及对于只在一个串中出现的字符的考虑等等，细节参考代码

#include #include #include #include using namespace std;const int maxn = 5010;const int INF = 0x3f3f3f3f;char c1[maxn], c2[maxn];int T, n1, n2, s1[26], e1[26], s2[26], e2[26];int dp[maxn][maxn], cnt[maxn][maxn];void init() { n1 = strlen(c1+1); n2 = strlen(c2+1); memset(s1, INF, sizeof(s1)); memset(s2, INF, sizeof(s2)); memset(e1, -1, sizeof(e1)); memset(e2, -1, sizeof(e2)); for (int i = 0; i < 26; i++) { for (int j = 1; j <= n1; j++) if (c1[j] == 'A'+i) { s1[i] = j; break; } for (int j = n1; j >= 1; j--) if (c1[j] == 'A'+i) { e1[i] = j; break; } for (int j = 1; j <= n2; j++) if (c2[j] == 'A'+i) { s2[i] = j; break; } for (int j = n2; j >= 1; j--) if (c2[j] == 'A'+i) { e2[i] = j; break; } }}void solve() { cnt[0][0] = 0; dp[0][0] = 0; for (int i = 0; i <= n1; i++) { for (int j = 0; j <= n2; j++) { if (i == 0 && j == 0) continue; dp[i][j] = INF; if (i) { int x = c1[i]-'A', t = cnt[i-1][j]; if (i == s1[x] && j < s2[x]) t++; if (i == e1[x] && j >= e2[x]) t--; dp[i][j] = dp[i-1][j]+t; cnt[i][j] = t; } if (j) { int x = c2[j]-'A', t = cnt[i][j-1]; if (j == s2[x] && i < s1[x]) t++; if (j == e2[x] && i >= e1[x]) t--; if (dp[i][j] > dp[i][j-1]+t) { dp[i][j] = dp[i][j-1]+t; cnt[i][j] = t; } else if (dp[i][j] == dp[i][j-1]+t) { cnt[i][j] = min(cnt[i][j], t); } } } }}int main() { scanf("%d", &T); getchar(); while (T--) { gets(c1+1); gets(c2+1); init(); solve(); printf("%d\n", dp[n1][n2]); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。