題意：現給定一個字符集中一共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\n", 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; }

?

轉載于:https://www.cnblogs.com/Lyush/p/3206645.html

總結

以上是生活随笔為你收集整理的ZOJ-2366 Weird Dissimilarity 动态规划+贪心的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。