http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=825&page=show_problem&problem=4500

状态:dp[i][j] 表示两个队列分别取前i个和前j个时,对最终结果的「贡献值」(指已在队列但尚未结束的颜色到i,j的距离之和)。
要计算这一「贡献值」,必须要记录每一颜色在两队列中的开始和结束位置。
转移:dp[i][j] = min(dp[i-1][j] + c[i-1][j], dp[i][j-1] + c[i][j-1]),其中c[i][j]表示此时已在队列但尚未结束的颜色个数

/*0.018s*/
const int mx = 5005;

char p[mx], q[mx];
int sp[26], sq[26], ep[26], eq[26];
int dp[2][mx], c[2][mx]; /// 用c[i][j]表示进行到i,j位置时,还剩下多少未匹配的颜色,可以用滚动数组优化

int solve(int n, int m)
{
    int t = 0;
    memset(c, 0, sizeof(c));
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= m; j++)
        {
            if (i == 0 && j == 0) continue;
            int v1 = inf, v2 = inf;
            if (i) v1 = dp[t ^ 1][j] + c[t ^ 1][j]; // 请把 t^1 视作 i-1,t 视作 i
            if (j) v2 = dp[t][j - 1] + c[t][j - 1];
            dp[t][j] = min(v1, v2);
            if (i)
            {
                c[t][j] = c[t ^ 1][j];
                if (sp[p[i]] == i && sq[p[i]] > j) c[t][j]++;
                if (ep[p[i]] == i && eq[p[i]] <= j) c[t][j]--;
            }
            else if (j)
            {
                c[t][j] = c[t][j - 1];
                if (sq[q[j]] == j && sp[q[j]] > i) c[t][j]++;
                if (eq[q[j]] == j && ep[q[j]] <= i) c[t][j]--;
            }
        }
        t ^= 1;
    }
    return dp[t ^ 1][m];
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%s%s", p + 1, q + 1);
        int n = strlen(p + 1);
        int 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;
        for (int i = 1; i <= n; i++) Qmin(sp[p[i]], i), ep[p[i]] = i;
        for (int i = 1; i <= m; i++) Qmin(sq[q[i]], i), eq[q[i]] = i;
        printf("%d\n", solve(n, m));
    }
    return 0;
}

Comments

comments powered by Disqus