输入两个长度分别是n和m(n,m<=5000)的颜色序列，要求按顺序合并成同一个序列，即每次可以把一个序列开头的颜色放到新序列的尾部。
例如，两个颜色序列GBBY和YRRGB，至少有两种合并结果：GBYBRYRGB和YRRGGBBYB。对于每种颜色来说其跨度L(c)等于最大位置和最小位置之差。例如，对于上面两种合并结果，每种颜色的L(c)和所有L(c)的总和，如图所示
Color G Y B R -> Sum L(c)Scenario 1 7 3 7 2 -> 19 L(c)scenario 2 1 7 3 1 -> 12 你的任务是找一种合并方式，使得所有L(c)的总和最小
设f（i，j）表示已经移走了i和j个元素还需要的费用
开始看题不够仔细，瞎推了一个转移方程，f（i，j）=min（f（i-1，j）+n-j+1，f（i，j+1）+n-i+1）
结果：
重新推
预处理每个颜色的开始与结束位置，每次累加L（c）值
1 #include2 #include 3 #include 4 using namespace std; 5 const int maxn=5000+5; 6 const int INF=1e9+7; 7 int num[2][maxn],sa[maxn],sb[maxn],ea[maxn],eb[maxn]; 8 int t,t1,t2,n,m,f[2][maxn]; 9 char a[maxn],b[maxn];10 template void red(t &x)11 {12 x=0;13 int w=1;14 char ch=getchar();15 while(ch<'0'||ch>'9')16 {17 if(ch=='-')18 w=-1;19 ch=getchar();20 }21 while(ch>='0'&&ch<='9')22 {23 x=(x<<3)+(x<<1)+ch-'0';24 ch=getchar();25 }26 x*=w;27 }28 void input()29 {30 freopen("input.txt","r",stdin);31 }32 int main()33 {34 //input();35 red(t);36 while(t--)37 {38 scanf("%s",a+1);39 scanf("%s",b+1); 40 n=strlen(a+1);41 m=strlen(b+1);42 memset(f,0,sizeof(f));43 //memset(color,0,sizeof(color));44 //memset(q,0,sizeof(q));45 memset(num,0,sizeof(num));46 memset(sa,0x3f,sizeof(sa));47 memset(sb,0x3f,sizeof(sb));48 memset(ea,0,sizeof(ea));49 memset(eb,0,sizeof(eb));50 for(int i=1;i<=n;++i)51 {52 a[i]-='A';53 sa[a[i]]=min(sa[a[i]],i);54 ea[a[i]]=i;55 }56 for(int i=1;i<=m;++i)57 {58 b[i]-='A';59 sb[b[i]]=min(sb[b[i]],i);60 eb[b[i]]=i;61 }62 for(int i=0;i<=n;++i)63 for(int j=0;j<=m;++j)64 {65 if(!i&&!j)66 continue;67 t1=t2=0x3f3f3f3f;68 if(i)69 t1=f[(i-1)%2][j]+num[(i-1)%2][j];70 if(j)71 t2=f[i%2][j-1]+num[i%2][j-1];72 f[i%2][j]=min(t1,t2);73 if(i)74 {75 num[i%2][j]=num[(i-1)%2][j];76 if(sa[a[i]]==i&&sb[a[i]]>j)77 ++num[i%2][j];78 if(ea[a[i]]==i&&eb[a[i]]<=j)79 --num[i%2][j];80 }81 else if(j)82 {83 num[i%2][j]=num[i%2][j-1];84 if(sb[b[j]]==j&&sa[b[j]]>i)85 ++num[i%2][j];86 if(eb[b[j]]==j&&ea[b[j]]<=i)87 --num[i%2][j];88 }89 }90 printf("%d\n",f[n%2][m]); 91 }92 return 0;93 }