题意：
字符c1和c2的距离为d(c1, c2)，已知两个字符串s和t，现在要找长度相等的两个字符串a和b，使得s是a的子序列，t是b的子序列，，且a和b的距离最小。
思路：
字串和子序列是不一样的。。。。子序列是允许中间 间断 的，而字串必须是连续的…比赛的时候居然理解错了….T_T
这样的话，用最长公共子序列的思路来解决这道题就好啦~
dp[i][j]表示 “第一个串处理到第i个字符，第二个串处理到第j个字符” 时，最短的距离是什么。。
然后这种两个串的题目见的很多啦….很好转移啊！详见代码
后面用一些值需要预处理一下然后保存下来~、、
路径输出使题目变得麻烦了一些啊..再根据刚才DP求得的最优值dfs回去 然后记录结果就好啦~
code：
#include<cstdio>#include<cstring>#include<cstdlib>#include<string>#include<vector>#include<algorithm>using namespace std;#define INF 0x3f3f3f3f//———————————–const int maxn = 2005;int z[maxn], lz;int s[maxn], ls, t[maxn], lt;int dist[maxn][maxn], va[maxn], vb[maxn];int f[maxn][maxn];int ansa[maxn*2], ansb[maxn*2], ca[maxn], cb[maxn], cnt;void change(char *ss, int *tmp){int len = strlen(ss);for(int i = 0; i < len; i++){tmp[i+1] = ss[i];}}void init(){char tmp[maxn];scanf("%s", tmp);lz = strlen(tmp);change(tmp, z);scanf("%s", tmp);ls = strlen(tmp);change(tmp, s);scanf("%s", tmp);lt = strlen(tmp);change(tmp, t);int u, v;for(int i = 1; i <= lz; i ++){u = z[i];for(int j = 1; j <= lz; j++){v = z[j];scanf("%d",&dist[u][v]);}}memset(va, INF, sizeof(va));memset(vb, INF, sizeof(vb));for(int i = 1; i <= lz; i++){for(int j = 1; j <= lz; j++){u = z[i], v = z[j];if(va[u] > dist[u][v]){va[u] = dist[u][v];ca[u] = v;}if(vb[u] > dist[v][u]){vb[u] = dist[v][u];cb[u] = v;}//va[u] = min(va[u], dist[u][v]);//vb[u] = min(vb[u], dist[v][u]);}}}int DP(int i, int j){if(f[i][j] != INF) return f[i][j];if(i == 0 && j == 0) return f[i][j] = 0;if(i > 0) f[i][j] = min(f[i][j], DP(i-1, j) + va[s[i]]);if(j > 0) f[i][j] = min(f[i][j], DP(i, j-1) + vb[t[j]]);if(i > 0 && j > 0) f[i][j] = min(f[i][j], DP(i-1, j-1) + dist[s[i]][t[j]]);return f[i][j];}void dfs(int i, int j){int ans = f[i][j];if(i > 0 && j > 0 && ans == f[i-1][j-1] + dist[s[i]][t[j]]){ansa[cnt] = s[i];ansb[cnt] = t[j];cnt++;dfs(i-1, j-1);return;}if(i > 0 && ans == f[i-1][j] + va[s[i]]){ansa[cnt] = s[i];ansb[cnt] = ca[s[i]];cnt++;dfs(i-1, j);return;}if(j > 0 && ans == f[i][j-1] + vb[t[j]]){ansa[cnt] = cb[t[j]];ansb[cnt] = t[j];cnt++;dfs(i, j-1);return ;}}void solve(){memset(f, INF, sizeof(f));int ans = DP(ls, lt);printf("%d\n",ans);cnt = 0;dfs(ls, lt);for(int i = cnt-1; i >= 0; i–){printf("%c",ansa[i]);}printf("\n");for(int i = cnt-1; i >= 0; i–){printf("%c",ansb[i]);}printf("\n");}int main(){init();solve();return 0;}
ps 可以学到路径打印的思路~~
然后这种两行的题目真的是见了许多了….然而并不怎么会….昨晚题目一定要注意多想想啦。。。
比赛的时候队友读错题真的是没办法….自己拿到题目要先确认一下呀..T_T。。。sigh…
版权声明：本文为博主原创文章，未经博主允许不得转载。
看着你手中的戒指，你说，你可以把它取下来吗？
