题面在这里

description

输入两个长度分别为\(n\)和\(m\)的颜色序列,要求按顺序合并成同一个序列,即每次可以把一个序列开头的颜色放到新序列的尾部。

对于每个颜色\(c\)来说,其跨度\(L(c)\)等于最大位置和最小位置之差。

你的任务是找一种合并方式,使得所有\(L(c)\)的总和最小。

——摘自《算法竞赛入门经典(第2版)》,刘汝佳著

data range

\[n,m\le 5000
\]

solution

序列合并问题,使用\(f[i][j]\)表示第一个序列前\(i\)个颜色和第二个序列前\(j\)个颜色合并之后的最小贡献

转移时每次往后添加两个序列首端的其中一个字符;

虽然通过这种状态无法得知每种颜色在这些方案中的始末位置,但我们仍然可以计算答案——未来费用的动态规划问题,提前计算贡献!

即每次往序列尾端添上一个颜色的时候,我们可以提前加上仍未终结的颜色的贡献

我们使用辅助数组\(g[i][j]\)表示第一个序列前\(i\)个颜色和第二个序列前\(j\)个颜色合并之后还未结束的颜色数量,于是可以这样转移:

\[f[i][j]=min\{f[i-1][j]+g[i-1][j],f[i][j-1]+g[i][j-1]\}
\]

答案存储在\(f[n][m]\),做完啦

code

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<iomanip>

#include<cstring>

#include<complex>

#include<vector>

#include<cstdio>

#include<string>

#include<bitset>

#include<cmath>

#include<queue>

#include<stack>

#include<map>

#include<set>

//#define TEST

#define FILE "a"

#define mp make_pair

#define pb push_back

#define RG register

#define il inline

using namespace std;

typedef unsigned long long ull;

typedef vector<int>VI;

typedef long long ll;

typedef double dd;

const int inf=1e9+7;

const int mod2=998244353;

const int rev2=332748118;

const int mod1=1e9+7;

const int N=5010;

const dd eps=1e-10;

const ll INF=1e18;

il ll read(){

  RG ll data=0,w=1;RG char ch=getchar();

  while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();

  if(ch=='-')w=-1,ch=getchar();

  while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar();

  return data*w;

}

il void file(){

  freopen(FILE".in","r",stdin);

  freopen(FILE".out","w",stdout);

}

int n,m,g[N][N],f[N][N],tot[400],cnt[400];

char a[N],b[N];

il int solve(){

	memset(tot,0,sizeof(tot));

	for(RG int i=1;i<=n;i++)tot[a[i]]++;

	for(RG int i=1;i<=m;i++)tot[b[i]]++;

	for(RG int i=0;i<=n;i++){

		memset(cnt,0,sizeof(cnt));

		g[i][0]=0;

		for(RG int j=1;j<=i;j++){

			if(!cnt[a[j]])g[i][0]++;

			cnt[a[j]]++;

			if(cnt[a[j]]==tot[a[j]])g[i][0]--;

		}

		for(RG int j=1;j<=m;j++){

			g[i][j]=g[i][j-1];

			if(!cnt[b[j]])g[i][j]++;

			cnt[b[j]]++;

			if(cnt[b[j]]==tot[b[j]])g[i][j]--;

		}

	}

	f[0][0]=0;

	for(RG int i=0;i<=n;i++)

		for(RG int j=0;j<=m;j++){

			if(i||j)f[i][j]=2147484647/2;

			if(i)f[i][j]=min(f[i][j],f[i-1][j]+g[i-1][j]);

			if(j)f[i][j]=min(f[i][j],f[i][j-1]+g[i][j-1]);

		}

	return f[n][m];

}

int main()

{

	RG int T=read();

	while(T--){

		scanf("%s%s",a+1,b+1);n=strlen(a+1);m=strlen(b+1);

		printf("%d\n",solve());

	}

	return 0;

}

巴特西

[UVA1625]Color Length

description

data range

solution

code

最新文章

热门文章