题意：现给定一个字符集中一共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 = ;
const int N = ;
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<<], qb[N<<];
// wa、wb数组分别用来说明sa串中的某字符的最佳匹配和sb串中某字符的最佳匹配
// ca、cb数组记录在wa、wb数组取得最优解的情况下所对应的字符 void dfs(int i, int j) {
if (!i && !j) return;
if (i > && j > && dp[i][j] == dp[i-][j-] + d[sa[i]][sb[j]]) {
qa[idxa++] = str[sa[i]];
qb[idxb++] = str[sb[j]];
dfs(i-, j-);
} else if (i > && dp[i][j] == dp[i-][j] + wa[sa[i]]){
qa[idxa++] = str[sa[i]];
qb[idxb++] = str[ca[sa[i]]];
dfs(i-, j);
} else {
qa[idxa++] = str[cb[sb[j]]];
qb[idxb++] = str[sb[j]];
dfs(i, j-);
}
} void gao() {
// 最坏情况需要构造出长度为la+lb长度的串
memset(dp, 0x3f, sizeof (dp));
dp[][] = ;
for (int i = ; i <= la; ++i) {
for (int j = ; j <= lb; ++j) {
if (i > ) {
dp[i][j] = min(dp[i][j], dp[i-][j] + wa[sa[i]]);
}
if (j > ) {
dp[i][j] = min(dp[i][j], dp[i][j-] + wb[sb[j]]);
}
if (i > && j > ) {
dp[i][j] = min(dp[i][j], dp[i-][j-] + d[sa[i]][sb[j]]);
}
}
}
printf("%d\n", dp[la][lb]);
idxa = idxb = ;
dfs(la, lb);
for (int i = idxa-; i >= ; --i) {
putchar(qa[i]);
}
puts("");
for (int i = idxb-; i >= ; --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+);
int len = strlen((char*)(str+));
for (int i = ; i <= len; ++i) {
mp[str[i]] = i;
}
scanf("%s %s", sa+, sb+);
la = strlen((char *)(sa+)), lb = strlen((char *)(sb+));
for (int i = ; i <= la; ++i) {
sa[i] = mp[sa[i]];
}
for (int i = ; i <= lb; ++i) {
sb[i] = mp[sb[i]];
}
for (int i = ; i <= len; ++i) {
for (int j = ; 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 ;
}