思路還算明白，不過要落實到代碼上還真敲不出來。

題意：

有兩個由大寫字母組成的顏色序列，將它們合并成一個序列：每次可以把其中一個序列開頭的顏色放到新序列的尾部。

對于每種顏色，其跨度定義為合并后的序列中最后一次和第一次出現的位置之差，求所有合并方案中所有顏色跨度之和的最小值。

分析：

d(i, j)表示兩個串分別已經移走了i個和j個字符。那么無論新串的順序是什么，有多少種顏色已經開始但尚未結束是確定的，記為c(i, j)。再繼續移走一個字符，所有顏色跨度之和就增加c(i, j)。c的計算是通過記錄每種顏色在每個串的始末位置來確定的。

由于數據量較大，還用滾動數組來優化空間復雜度。

?

1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 8 const int maxn = 5000 + 10; 9 const int INF = 1000000000; 10 char p[maxn], q[maxn]; 11 int sp[26], ep[26], sq[26], eq[26]; //記錄兩個串每種顏色的始末 12 int d[2][maxn], c[2][maxn]; //c[i][j]表示d[i][j]時還有多少種顏色已經開始但尚未結束 13 14 int main(void) 15 { 16 #ifdef LOCAL 17 freopen("1625in.txt", "r", stdin); 18 #endif 19 20 int n, m, T; 21 scanf("%d", &T); 22 while(T--) 23 { 24 scanf("%s", p+1); 25 scanf("%s", q+1); 26 n = strlen(p+1); 27 m = strlen(q+1); 28 for(int i = 1; i <= n; ++i) p[i] -= 'A'; 29 for(int i = 1; i <= m; ++i) q[i] -= 'A'; 30 31 for(int i = 0; i < 26; ++i) { sp[i] = sq[i] = INF; ep[i] = eq[i] = 0; } 32 for(int i = 1; i <= n; ++i) 33 { 34 sp[p[i]] = min(sp[p[i]], i); 35 ep[p[i]] = i; 36 } 37 for(int i = 1; i <= m; ++i) 38 { 39 sq[q[i]] = min(sq[q[i]], i); 40 eq[q[i]] = i; 41 } 42 43 int t = 0; 44 memset(d, 0, sizeof(d)); 45 memset(c, 0, sizeof(c)); 46 for(int i = 0; i <= n; ++i) 47 { 48 for(int j = 0; j <= m; ++j) 49 { 50 if(!i && !j) continue; 51 52 int v1, v2; 53 v1 = v2 = INF; 54 if(i) v1 = d[t^1][j] + c[t^1][j]; 55 if(j) v2 = d[t][j-1] + c[t][j-1]; 56 d[t][j] = min(v1, v2); 57 //計算c 58 if(i) 59 { 60 c[t][j] = c[t^1][j]; 61 if(sp[p[i]] == i && sq[p[i]] > j) c[t][j]++; 62 if(ep[p[i]] == i && eq[p[i]] <= j) c[t][j]--; 63 } 64 else if(j) 65 { 66 c[t][j] = c[t][j-1]; 67 if(sq[q[j]] == j && sp[q[j]] > i) c[t][j]++; 68 if(eq[q[j]] == j && ep[q[j]] <= i) c[t][j]--; 69 } 70 } 71 t ^= 1; 72 } 73 printf("%d\n", d[t^1][m]); 74 } 75 76 return 0; 77 } 代碼君

?

轉載于:https://www.cnblogs.com/AOQNRMGYXLMV/p/4006498.html

總結

以上是生活随笔為你收集整理的UVa 1625 Color Length的全部內容，希望文章能夠幫你解決所遇到的問題。

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