紫书 例题 9-8 UVa 1625 (滚动数组+公共字符串处理）

这题看题解看了很久，学到了挺多（自己还是太弱，唉！）

（1）这道题的思路非常的巧妙。我一开始看到就觉得不好来记录开始位置以及

结束位置。但是题解换了一个思路，记录每一次开始了但还没有结束的字符有多少个

这样每次进来一个新的字符，就可以更新答案。

（2）这一类两个字符串取公共部分的题，有一个大概的套路。

可以设f[i][j]为第一个字符串用了前i个，第二个字符串用了前j个的情况

然后转移的时候用f[i-1][j]和f[i][j-1]进行处理

（3）滚动数组省空间。当数组只涉及到最近几层的时候可以用滚动数组

比如01背包，每次只需要用到上一行的，所以直接用一维就ok，只是枚举要逆序

然而这道题的转移，不仅涉及到当前一层，还涉及到上一层(d[i-1][j]与c[i][j-1])

所以要用两个数组，用t不断取异或变成0和1来维护。

摸板大致是这样

int t = 0;  //初始化 
memset()    //数组清空 
REP(i, 0, n)
{
	REP(j, 0, m)
	{
		i     -> t         //当前这一层 
		i - 1 -> t ^ 1     //上一层 
	}
	t ^= 1;
}
printf("%d\n", f[t^1][m-1]); //最后是t ^ 1 
//t是当前这一层,但是最后t又异或了一次，所以是t ^ 1 

（4）在动规题目中字符串从1开始比较方便，例如0的位置可以用来初始化，表示这个字符串没有的时候

 

#include<cstdio>
#include<algorithm>
#include<cstring>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;

const int MAXN = 5123;
char p[MAXN], q[MAXN];
int sp[26], ep[26], sq[26], eq[26];
int d[2][MAXN], c[2][MAXN]; 

int main()
{
	int n, m, T;
	scanf("%d", &T);
	
	while(T--)
	{
		scanf("%s%s", p + 1, q + 1);
		int n = strlen(p + 1), m = strlen(q + 1);
		REP(i, 1, n + 1) p[i] -= 'A';
		REP(i, 1, m + 1) q[i] -= 'A';
		
		REP(i, 0, 26)
		{
			sp[i] = sq[i] = 1e9;
			ep[i] = eq[i] = 0;
		}
		REP(i, 1, n + 1)
		{
			sp[p[i]] = min(sp[p[i]], i);
			ep[p[i]] = i;
		}
		REP(i, 1, m + 1)
		{
			sq[q[i]] = min(sq[q[i]], i);
			eq[q[i]] = i;
		}
		
		int t = 0;
		memset(c, 0, sizeof(c));
		memset(d, 0, sizeof(d));
		REP(i, 0, n + 1)
		{
			REP(j, 0, m + 1)
			{
				if(!i && !j) continue;
				int v1 = 1e9, v2 = 1e9;
				if(i) v1 = d[t ^ 1][j] + c[t ^ 1][j];
				if(j) v2 = d[t][j - 1] + c[t][j - 1];
				d[t][j] = min(v1, v2);
				
				if(i)
				{
					c[t][j] = c[t ^ 1][j];
					if(sp[p[i]] == i && sq[p[i]] > j) c[t][j]++;  //公共串中第一次出现 
					if(ep[p[i]] == i && eq[p[i]] <= j) c[t][j]--; //公共串中最后一次出现 
				}
				else if(j)
				{
					c[t][j] = c[t][j - 1];
					if(sq[q[j]] == j && sp[q[j]] > i) c[t][j]++; //同上 
					if(eq[q[j]] == j && ep[q[j]] <= i) c[t][j]--;
				}
			}
			t ^= 1;
		}
			
		printf("%d\n", d[t^1][m]);
	}
	
	return 0;
}