轉載

http://www.mzry1992.com/blog/miao/uestc-summer-team-training-1.html

有两队车（长度5000）要合成一队，每次只能在两队队头出队一辆。

每辆车有一种颜色，用A-Z表示。

一队车的权值就是每一种颜色在队列中出现的第一辆车和出现的最后一辆车的位置差之和。

求安排方案使得权值最小。

。。。。

对于每一种颜色假如在队列中出现的第一辆车位置为opi，最后一辆车位置为edi。

那么就是求min(sigma{edi-opi})。

用dp[i][j]表示第一列车出队i辆，第二列车出队j辆，转移如下：

• dp[i+1][j] = min(dp[i+1][j],dp[i][j]+isend()-isbegin())
• dp[i][j+1] = min(dp[i][j+1],dp[i][j]+isend()-isbegin())

isend()函数表示选择出队的车出队后后面就没有该颜色的车了，那么就要加上对应车在答案序列中的位置。

isbegin()函数表示选择出队的车出队之前没有该颜色的车，那么就要减去对应车在答案序列中的位置。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define L 5005
using namespace std;
char a[L], b[L];
int la, lb;
int dp[L][L], ta[L][26], tb[L][26];
int isEnd(int pa, int pb, char ch) {
    ch -= 'A';
    if(ta[pa][ch]+tb[pb][ch] == ta[la-1][ch]+tb[lb-1][ch])
        return pa+pb;
    return 0;
}
int isBegin(int pa, int pb, char ch) {
    ch -= 'A';
    if(ta[pa][ch] + tb[pb][ch] == 1)
        return pa+pb;
    return 0;
}
int main() {
    int t, i, j;
    scanf("%d", &t);
    getchar();
    while(t--) {
        a[0] = b[0] = ' ';
        gets(a+1);
        gets(b+1);
        la = strlen(a);
        lb = strlen(b);
        for(i = 0; i < 26; i++)
            ta[0][i] = tb[0][i] = 0;
        for(i = 1; i < la; i++) {
            for(j = 0; j < 26; j++)
                ta[i][j] = ta[i-1][j];
            ta[i][a[i]-'A']++;
        }
        for(i = 1; i < lb; i++) {
            for(j = 0; j < 26; j++)
                tb[i][j] = tb[i-1][j];
            tb[i][b[i]-'A']++;
        }
        for(i = 0; i < la; i++)
            for(j = 0; j < lb; j++)
                dp[i][j] = 1<<30;
        dp[0][0] = 0;
        for(i = 0; i < la; i++) {
            for(j = 0; j < lb; j++) {
                dp[i+1][j] = min(dp[i+1][j], dp[i][j]+isEnd(i+1, j, a[i+1])-isBegin(i+1, j, a[i+1]));
                dp[i][j+1] = min(dp[i][j+1], dp[i][j]+isEnd(i, j+1, b[j+1])-isBegin(i, j+1, b[j+1]));
            }
        }
        printf("%d\n", dp[la-1][lb-1]);
    }
    return 0;
}