首页 > 代码库 > UVa 1625 Color Length
UVa 1625 Color Length
思路还算明白，不过要落实到代码上还真敲不出来。
题意：
有两个由大写字母组成的颜色序列，将它们合并成一个序列：每次可以把其中一个序列开头的颜色放到新序列的尾部。
对于每种颜色，其跨度定义为合并后的序列中最后一次和第一次出现的位置之差，求所有合并方案中所有颜色跨度之和的最小值。
分析：
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 LOCAL17 freopen("1625in.txt", "r", stdin);18 #endif19 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 //计算c58 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 }
UVa 1625 Color Length
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。