紫书例题 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;

}

巴特西

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

最新文章

热门文章

巴特西

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

最新文章

热门文章

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