// uva1625 Color Length// 这是好久之前在紫书(page 276)上看到的题目了// 题目的意思是，给你两个长度分别为n和m的颜色序列(n,m<=5000)// 都是由大写字母组成，要求按照顺序合并成同一个序列，即每次// 可以把一个序列开头的颜色放在新序列的尾部// 比如两个序列:GGBY 和 YRRGB至少有两种合并结果:// GBYBRYRGB 和 YRRGGBBYB 对于每一种颜色c，跨度L(c)是最大位置和// 最小位置之差，// 问题是： 找一种合并的方式使得L(c)的总和最小。//// 首先，要换一种思维，每种颜色分别记录最小位置和最大位置，这个是不会有错的// 之后，我们不是每种颜色单独去统计每次出现这种颜色时，他的最开始的位置，然// 后再去加上此时的长度，而是所有颜色一起统计在第一个串i的位置和在第二个串j// 的位置未结束但是已经开始的颜色的总数，因为最后统计的总的sigema(L)的时候// 这些位置都是要算进去的// 则：状态d(i,j)表示第一个串剩下i和第二个串剩下j时所得到的sigma(L)的最小值// 则状态转移为:d(i,j) = min(d(i+1,j),d(i,j+1))+res(i,j);// d(i+1,j)表示从第一个串拿走一个// d(i,j+1)表示从第二个串拿走一个// res(i,j)表示当前第一个串i，第二个串j位置时未结束但是已经开始的颜色的总数//////// 感悟：// 这道题真的看了很久很久，想了很久很久，，看着书上的记录开始和结束的位置// 我还能懂，之后计数的环节我就不太懂了，书上的代码我也没有看懂// 目前只会这种状态的定义，而且细节部分还要多多的考究，会把紫书上的状态// 再仔细的研习的，也望各位能够给予指点，小子实在是感激不尽// 哎，继续练吧。。。// #include <algorithm>#include <bitset>#include <cassert>#include <cctype>#include <cfloat>#include <climits>#include <cmath>#include <complex>#include <cstdio>#include <cstdlib>#include <cstring>#include <ctime>#include <deque>#include <functional>#include <iostream>#include <list>#include <map>#include <numeric>#include <queue>#include <set>#include <stack>#include <vector>#define ceil(a,b) (((a)+(b)-1)/(b))#define endl '\n'#define gcd __gcd#define highBit(x) (1ULL<<(63-__builtin_clzll(x)))#define popCount __builtin_popcountlltypedef long long ll;using namespace std;const int MOD = 1000000007;const long double PI = acos(-1.L);template<class T> inline T lcm(const T& a, const T& b) { return a/gcd(a, b)*b; }template<class T> inline T lowBit(const T& x) { return x&-x; }template<class T> inline T maximize(T& a, const T& b) { return a=a<b?b:a; }template<class T> inline T minimize(T& a, const T& b) { return a=a<b?a:b; }const int maxn = 5010;int d[maxn][maxn];char p[maxn],q[maxn];int len1,len2;int start[27][2];int end[27][2];int res[maxn][maxn];const int inf = 0x3f3f3f3f;void print(){for (int i=0;i<len1;i++){for (int j=0;j<len2;j++)printf("%d ",d[i][j]);puts("");}}void init(){scanf("%s",p);scanf("%s",q);len1 = strlen(p);len2 = strlen(q);for (int i=0;i<=len1;i++)for (int j=0;j<=len2;j++)d[i][j] = inf;memset(start,0x3f,sizeof(start));memset(end,-1,sizeof(end));for (int i=0;i<len1;i++){p[i] -= 'A';}for (int i=0;i<len2;i++)q[i] -= 'A';for (int i=0;i<len1;i++){if (start[p[i]][0] == inf)start[p[i]][0] = i;end[p[i]][0] = i;}for (int i=0;i<len2;i++){if (start[q[i]][1] == inf)start[q[i]][1] = i;end[q[i]][1] = i;}for (int i=0;i<=len1;i++)for (int j=0;j<=len2;j++){int cnt = 0;for (int k=0;k<26;k++){if (start[k][0]==inf&&start[k][1]==inf)continue;if (start[k][0]>i-1&&start[k][1]>j-1)continue;if (end[k][0]<i&&end[k][1]<j)continue;cnt++;}res[i][j] = cnt;}}void solve(){d[len1][len2]=0;//print();for (int i=len1-1;i>=0;i–)d[i][len2] = d[i+1][len2]+res[i][len2];for (int j=len2-1;j>=0;j–)d[len1][j] = d[len1][j+1]+res[len1][j];for (int i=len1-1;i>=0;i–)for (int j=len2-1;j>=0;j–)d[i][j] = min(d[i+1][j],d[i][j+1])+res[i][j];printf("%d\n",d[0][0]);//print();}int main() {int t;//freopen("G:\\Code\\1.txt","r",stdin);scanf("%d",&t);while(t–){init();solve();}return 0;}
游手好闲会使人心智生锈
