转载自blogs./zyb993963526/p/6364069.html
题意:
输入两个长度分别为n和m的颜色序列,要求按顺序合并成同一个序列,即每次可以把一个序列开头的颜色放到新序列的尾部。对于每个颜色c来说,其跨度L(c)等于最大位置和最小位置之差。
思路:
我们用d(i,j)表示两个序列已经分别移走了i和j个元素时的最小代价。当然为了在状态转移时知道每个字母的状态,我们需要一些预处理。在下面的代码中,sp,ep数组分别用来表示序列1中每个字母的开头位置和结束位置,同样的,sq,eq分别用来表示序列1中每个字母的开头位置和结束位置。每次新增一个字符后,所有已经出现的但没有结束的字符的跨度L(c)都要+1。所以,我们还需要设置一个c数组来记录已经开始但还没有结束的字符数。
这样,转移方程就是dp(i,j)=min(dp(i-1,j)+c[i-1][j],dp(i,j-1)+c[i][j-1])。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;const int maxn = 5000 + 5;
const int INF = 10000000;char p[maxn], q[maxn];
int sp[26], sq[26], ep[26], eq[26];
int d[maxn][maxn], c[maxn][maxn];int main()
{//freopen("D:\\txt.txt", "r", stdin);int T, n, m;scanf("%d", &T);while (T--){scanf("%s%s", p + 1, q + 1);//cout << p + 1 << " " << q + 1 << endl;n = strlen(p + 1);m = strlen(q + 1);//将字母转化成数字for (int i = 1; i <= n; i++) p[i] -= 'A';for (int i = 1; i <= m; i++) q[i] -= 'A';//预处理for (int i = 0; i < 26; i++){sp[i] = sq[i] = INF;ep[i] = eq[i] = 0;}//预处理,计算出序列1中每个字符的开始位置和结束位置for (int i = 1; i <= n; i++){sp[p[i]] = min(sp[p[i]], i);ep[p[i]] = i;}//预处理序列2for (int i = 1; i <= m; i++){sq[q[i]] = min(sq[q[i]], i);eq[q[i]] = i;}for (int i = 0; i <= n; i++){for (int j = 0; j <= m; j++){if (!i && !j) continue;int v1 = INF, v2 = INF;if (i) v1 = d[i-1][j] + c[i-1][j]; //从p中取颜色if (j) v2 = d[i][j - 1] + c[i][j - 1]; //从q中取颜色d[i][j] = min(v1, v2);//更新c数组if (i){c[i][j] = c[i - 1][j];if (sp[p[i]] == i && sq[p[i]] > j) c[i][j]++;if (ep[p[i]] == i && eq[p[i]] <= j) c[i][j]--;}else if (j){c[i][j] = c[i][j - 1];if (sq[q[j]] == j && sp[q[j]] > i) c[i][j]++;if (eq[q[j]] == j && ep[q[j]] <= i) c[i][j]--;}}} cout << d[n][m] << endl;}return 0;
}
更多推荐
Color,Length,UVA
发布评论