UVa 1625

DP状态设计的思路是不难想到的，问题在于维护，每一个状态的计算，除了计算最小的和，我们同时也要记录颜色的使用情况。同时我们对于最小和的更新也必须匹配新的方法：

• 遍历颜色表，此前x颜色已经出现，那么此后，计算最小和，这个颜色就会贡献1个长度。
• 若是此前y颜色已经饱和了，也就是说明这个颜色的“线段”已经确定，那么他的L(c)便不会再增长。
• 每次状态转移都是从两个队列中取头元素的颜色，记得要将当前颜色状态表关于此颜色更新（相当于转移前状态对应颜色+1）

代码实现的时候，记录颜色的状态用了滚动数组，因为码力弱，所以编出来思考时间有点久，而且一个错误贡献了一个WA，数组开大点其实没有影响，代码实现思路更简洁，不过滚动数组空间优化还是可以的，O(nm)降到了O(n+m)。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
#include <vector>
using namespace std;

const int maxl= 5005;

char s1[maxl], s2[maxl];
int c[27];
int dp[maxl][maxl];
// count color and auxiliary count
int cc[maxl][27], ac[maxl][27];

void Init(int m, int n)
{
	int ix;
	memset(c, 0, sizeof(c));
	memset(cc, 0, sizeof(cc));
	memset(ac, 0, sizeof(ac));
	dp[0][0]= 0;

	for (int i= 1; i<= m; ++i){
		ix= s1[i]-'A';
		++c[ix];
	}
	for (int j= 1; j<= n; ++j){
		ix= s2[j]-'A';
		++c[ix];
	}

	for (int i= 1; i<= m; ++i){
		ix= s1[i]-'A';
		dp[i][0]= dp[i-1][0];

		for (int k= 0; k< 26; ++k){
			cc[i][k]= cc[i-1][k];
			if (cc[i-1][k] && (cc[i-1][k]< c[k])){
				++dp[i][0];
			}
		}
		++cc[i][ix];
	}
	for (int j= 1; j<= n; ++j){
		ix= s2[j]-'A';
		dp[0][j]= dp[0][j-1];

		for (int k= 0; k< 26; ++k){
			ac[j][k]= ac[j-1][k];
			if (ac[j-1][k] && (ac[j-1][k]< c[k])){
				++dp[0][j];
			}
		}
		++ac[j][ix];
	}
}

int main()
{
	int T, m, n;
	int ix, x;
	scanf("%d", &T);

	while (T--){
		scanf(" %s", s1+1);
		scanf(" %s", s2+1);
		m= strlen(s1+1);
		n= strlen(s2+1);

		Init(m, n);
		for (int j= 1; j<= n; ++j){
			for (int k= 0; k< 26; ++k){
				cc[0][k]= ac[j][k];
			}
			for (int i= 1; i<= m; ++i){
				ix= s2[j]-'A';
				dp[i][j]= dp[i][j-1];
				for (int k= 0; k< 26; ++k){
					if (cc[i][k] && (cc[i][k]< c[k])){
						++dp[i][j];
					}
				}

				x= dp[i-1][j];
				for (int k= 0; k< 26; ++k){
					if (cc[i-1][k] && (cc[i-1][k]< c[k])){
						++x;
					}
				}
				if (x< dp[i][j]){
					dp[i][j]= x;
					ix= s1[i]-'A';
					for (int k= 0; k< 26; ++k){
						cc[i][k]= cc[i-1][k];
					}
				}
				++cc[i][ix];
			}
		}
		cout<<dp[m][n]<<endl;
	}

	return 0;
}