dp专题-UVa-1625- 合并字符串使代价最小

题目链接：https://vjudge.net/contest/306591#problem/H
题目大意：输入两个长度分别为n和m的颜色序列，要求按顺序合并成同一个序列，即每次可以把一个序列开头的颜色放到新序列的尾部。对于每个颜色c来说，其跨度L（c）等于最大位置和最小位置之差。应使得合并成的序列中所有颜色的L（c）之和尽量小。

思路：
无后效性，但是这个代价条件想不出来怎么搞。参看紫书，理解了他的基本思想，但还是码不出来，无奈又看了代码。

可以想到用d[ i ][ j ] : 表示A序列的前 i 个字符并上 B序列的 j 个字符的最小代价。
可是这个代价怎么算？但从要知道他的跨度，就要知道他的始末位置，从状态里很难直接获得。这时需要转换计算代价的方式：不是等到一个颜色全部移动完之后再算，而是每次累加。当把某个颜色移动到最终序列前，需要把所有“已经出现但还没结束”的颜色的L（c）加一。这里的“还没结束”
指的是还没有到达这个颜色的最后位置，在最终序列中它可能已经出现了不止一次，但只要它还没有结束（后面还有），它就会给那些未结束的颜色代价加一，因为它横在了中间。

转：https://blog.csdn.net/CY05627/article/details/88369386

#include <bits/stdc++.h>
using namespace std;
const int INF = 1<<30;
const int N = 5005;
char s1[N], s2[N];
int L1[100], L2[100], R1[100], R2[100];
int d[N][N], num[N][N];
/* num[i][j] ：取走序列1的前 i 个字符，取走序列2中前 j 个字符，在最终序列中已经出现但未结束的字符个数。 d[i][j]：在两个序列中分别取走了前 i , j 个字符的最小代价。 L1[],R1[]：分别表示序列1中每个字符的开始位置和结束位置。b2,e2一样。 向最终序列新增加一个字符后（这个字符来自序列1或2的头部），所有已经出现但未结束的字符的跨度L(c)都要加一。 状态转移方程：dp[i][j] = min( dp[i-1][j] + num[i-1][j]，dp[i][j-1] + num[i][j-1] ）。 */

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s%s",s1+1,s2+1);
        int Len1=strlen(s1+1);
        int Len2=strlen(s2+1);
        for(int i='A';i<='Z';i++)
        {
            L1[i]=L2[i]=INF;
            R1[i]=R2[i]=0;
        }
        for(int i=1;i<=Len1;i++)
        {
            char c=s1[i];
            L1[c]=min(L1[c], i);
            R1[c]=max(R1[c], i);
        }
        for(int i=1;i<=Len2;i++)
        {
            char c=s2[i];
            L2[c]=min(L2[c], i);
            R2[c]=max(R2[c], i);
        }
        num[0][0]=0;
        for(int i=0;i<=Len1;i++)
        {
            for(int j=0;j<=Len2;j++)
            {
                if(i)
                {
                    num[i][j]=num[i-1][j];
                    char c=s1[i];
                    if(L1[c]==i&&L2[c]>j)//能确定s1[i]是第一字符c，因为s2[]中的第一个字符c还在s2中
                    {
                        ++num[i][j];
                    }
                    if(R1[c]==i&&R2[c]<=j)//能确定s1[i]是最后字符c，因为s2[]中的最后字符已经拿出来了
                    {
                        --num[i][j];
                    }

                }
                if(j)
                {
                    num[i][j]=num[i][j-1];
                    char c=s2[j];
                    if(L2[c]==j&&L1[c]>i)
                    {
                        ++num[i][j];
                    }
                    if(R2[c]==j&&R1[c]<=i)
                    {
                        --num[i][j];
                    }
                }
            }
        }
        for(int i=0;i<=Len1;i++)
        {
            for(int j=0;j<=Len2;j++)
            {
                if(i==0&&j==0) continue;
                d[i][j] = INF;
                if(i) d[i][j] = min(d[i][j], d[i-1][j] + num[i-1][j]);
                if(j) d[i][j] = min(d[i][j], d[i][j-1] + num[i][j-1]);

            }
        }

        printf("%d\n",d[Len1][Len2]);
    }

    return 0;
}

//滚动数组优化
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 1<<30;
const int N = 5005;
char s1[N], s2[N];
int b1[100], b2[100], e1[100], e2[100];
int num[2][N], d[2][N]; // 滚动数组
 
int main()
{
	
	//freopen("in.txt","r",stdin);
	int T; scanf("%d",&T);
	while(T--){
	
		scanf("%s\n%s",s1+1, s2+1);
		//printf("%s\n%s\n",s1+1,s2+1);
		int len1 = strlen(s1+1), len2 = strlen(s2+1),c;
		for(c = 'A'; c <= 'Z'; ++c) { b1[c] = b2[c] = INF; e1[c] = e2[c] = 0; }
		for(int i = 1; i <= len1; ++i){
			c = s1[i];
			b1[c] = min(i, b1[c]);
			e1[c] = i;
		}
		for(int i = 1; i <= len2; ++i){
			c = s2[i];
			b2[c] = min(i, b2[c]);
			e2[c] = i;
		}
	
		memset(d,0,sizeof(d));
		memset(num,0,sizeof(num));
		int t = 0;
		
		for(int i = 0; i <= len1; ++i){
			for(int j = 0; j <= len2; ++j){
				
				if(i==0&&j==0) continue;
				
				int v1 = INF, v2 = INF;
				if(i) v1 = d[t^1][j] + num[t^1][j];
				if(j) v2 = d[t][j-1] + num[t][j-1];
				d[t][j] = min(v1,v2);
				
				if(i){
					num[t][j] = num[t^1][j];
					c = s1[i];
					if(b1[c] == i&& b2[c] > j) ++num[t][j];
					if(e1[c] == i&& e2[c] <= j) --num[t][j];
				}
				if(j){
					num[t][j] = num[t][j-1];
					c = s2[j];
					if(b2[c] == j&& b1[c] > i) ++num[t][j];
					if(e2[c] == j&& e1[c] <= i) --num[t][j];
				}
			}
			t^= 1;
		}
		
		printf("%d\n",d[t^1][len2]);
	}

	return 0;
}