题意：现给定一个字符集中一共Z个元素的环境，给出一个Z*Z的数组，表示从i到j之间的距离。给定两组字符串，分别问包含着两个字符串（给定的字符串为所求字符串的子序列不是子串）对应位的距离和值最小为多少？输出这两个字符串。
分析：该题的状态还是比较好开设的，设dp[i][j]表示a串的前i个字符和b串的前j个字符被包含后的最小开销，于是动态转移方程：
dp[i][j] = min(dp[i][j], dp[i-1][j] + wa[sa[i]]); 其中wa数组表示某个字符与另外一个最小花费的字符匹配，sa[i]表示a串的第i个字符
dp[i][j] = min(dp[i][j], dp[i][j-1] + wb[sb[j]]); 意义同上一个转移类似，均表示一个字符与一个最便宜的字符匹配
dp[i][j] = min(dp[i][j], dp[i-1][j-1] + dist[sa[i]][sb[j]]); 该方程的意义为两个串均拿出一个字符来匹配
这里需要说明的是补全两个串的最长长度最多为两个串长度之和，由上面的转移可以知道，每个位至少会有一个字符是属于串a或者是串b。
还有一个地方要特别注意的是，给定字符集可能会有超过127的ascii码，并且编号之后可能有编号大于127，因此前面自己写的sa[i] = mp[sa[i]]一直RE就是出现了负数，改成了unsigned char了。
#include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <iostream> #include <map> using namespace std; const int Z = 256; const int N = 2005; int d[Z][Z]; map<char, int>mp; unsigned char str[Z], sa[N], sb[N]; int na[N], nb[N]; int la, lb, wa[Z], wb[Z], ca[Z], cb[Z]; int idxa, idxb, dp[N][N], path[N][N]; char qa[N<<1], qb[N<<1]; // wa、wb数组分别用来说明sa串中的某字符的最佳匹配和sb串中某字符的最佳匹配 // ca、cb数组记录在wa、wb数组取得最优解的情况下所对应的字符 void dfs(int i, int j) { if (!i && !j) return; if (i > 0 && j > 0 && dp[i][j] == dp[i-1][j-1] + d[sa[i]][sb[j]]) { qa[idxa++] = str[sa[i]]; qb[idxb++] = str[sb[j]]; dfs(i-1, j-1); } else if (i > 0 && dp[i][j] == dp[i-1][j] + wa[sa[i]]){ qa[idxa++] = str[sa[i]]; qb[idxb++] = str[ca[sa[i]]]; dfs(i-1, j); } else { qa[idxa++] = str[cb[sb[j]]]; qb[idxb++] = str[sb[j]]; dfs(i, j-1); } } void gao() { // 最坏情况需要构造出长度为la+lb长度的串 memset(dp, 0x3f, sizeof (dp)); dp[0][0] = 0; for (int i = 0; i <= la; ++i) { for (int j = 0; j <= lb; ++j) { if (i > 0) { dp[i][j] = min(dp[i][j], dp[i-1][j] + wa[sa[i]]); } if (j > 0) { dp[i][j] = min(dp[i][j], dp[i][j-1] + wb[sb[j]]); } if (i > 0 && j > 0) { dp[i][j] = min(dp[i][j], dp[i-1][j-1] + d[sa[i]][sb[j]]); } } } printf("%d ", dp[la][lb]); idxa = idxb = 0; dfs(la, lb); for (int i = idxa-1; i >= 0; --i) { putchar(qa[i]); } puts(""); for (int i = idxb-1; i >= 0; --i) { putchar(qb[i]); } puts(""); } int main() { int T; scanf("%d%", &T); while (T--) { mp.clear(); memset(wa, 0x3f, sizeof (wa)); memset(wb, 0x3f, sizeof (wb)); scanf("%s", str+1); int len = strlen((char*)(str+1)); for (int i = 1; i <= len; ++i) { mp[str[i]] = i; } scanf("%s %s", sa+1, sb+1); la = strlen((char *)(sa+1)), lb = strlen((char *)(sb+1)); for (int i = 1; i <= la; ++i) { sa[i] = mp[sa[i]]; } for (int i = 1; i <= lb; ++i) { sb[i] = mp[sb[i]]; } for (int i = 1; i <= len; ++i) { for (int j = 1; j <= len; ++j) { scanf("%d", &d[i][j]); if (wa[i] > d[i][j]) { wa[i] = d[i][j], ca[i] = j; } if (wb[j] > d[i][j]) { wb[j] = d[i][j], cb[j] = i; } } } gao(); } return 0; }