HDU7190多校 - BBQ

• 链接：http://acm.hdu.edu.cn/showproblem.php?pid=7190
• 知识点：DP、哈希
• 难度：紫

题意

• 给出一个字符串 $SS$，你可以进行如下 $33$ 种操作。
• 在任意位置添加字符；删除、修改任意字符。
• 你需要让 $SS$ 满足以下要求：
  • $\mathrm{\mid }S\mathrm{\mid }\mathrm{m}\mathrm{o}\mathrm{d}4=0|S|\; \backslash mod\; 4=0$
  • $s_i=s_{i+3}s\_i=s\_\{i+3\}$，$s_{i+1}=s_{i+2}s\_\{i+1\}=s\_\{i+2\}$ $(i\mathrm{m}\mathrm{o}\mathrm{d}4=1)(i\; \backslash mod\; 4=1)$，$ii$ 从 $11$ 开始。
• 问至少进行的操作次数。

思路

初步思路

• 编辑距离问题

• 给出一个原始串 $SS$ 和一个模式串 $TT$，每一步操作可以对原始串进行添加一个字符、删除一个字符、修改一个字符的操作。
• 问至少进行多少步操作能让 $SS$ 变为 $TT$。
• $dp[i][j]dp[i][j]$ 代表已经将 $SS$ 的前 $ii$ 位变成了 $TT$ 的前 $jj$ 位，所需的最少操作次数。
• 初始化：$dp[0][i]=idp[0][i]=i$，$dp[i][0]=idp[i][0]=i$
• 转移：$dp[i][j]=\min (dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+(S_i\mathrm{\ne }{T}_j))dp[i][j]=\; \backslash min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+(S\_i\backslash neq\; T\_j))$

• 显然本题直接使用编辑距离问题是不行的，数据范围过大，并且也没有目标串。
• 发现结论：
  • 一个合法的区间是 abba 的形式。
  • 要把一段串通过修改变成一个长度为 $44$ 的 abba 形式，要想操作次数最少，这个串的长度应该 $\le 7\backslash leq\; 7$。如果长度达到 $88$，那么至少操作 $44$ 步，那这样的话变成一个长度为 $88$ 的abbaabba 岂不是更好？
• 考虑 DP。$dp[i]dp[i]$ 代表以 $SS$ 的第 $ii$ 位为结尾的、之前都修改得符合要求的最少操作次数。
• 既然每次最多考虑 $77$ 位，$77$ 位的情况数并不多。

做法1

• 考虑枚举出 $1\mathrm{～}71～7$ 位的全部情况，计算将每种情况变成 abba 形式的最小操作次数。
• 预处理时，可以按照 $bin[hash]=\mathrm{最}\mathrm{少}\mathrm{操}\mathrm{作}\mathrm{次}\mathrm{数}bin[hash]=最少操作次数$ 的形式进行存储。
• DP转移：1.计算哈希转移 $dp[i]=\min (dp[i],dp[i-j]+bin[hash])dp[i]=\backslash min\; (dp[i],dp[i-j]+bin[hash])$。2.删除这个字符 $dp[i]=\min (dp[i],dp[i-1]+1)dp[i]=\backslash min(dp[i],dp[i-1]+1)$

做法2

• 考虑枚举出 $1\mathrm{～}71～7$ 位的全部情况，计算将每种情况变成 abba 形式或空串的最小操作次数。
• 预处理时，可以按照 $bin[hash]=\mathrm{最}\mathrm{少}\mathrm{操}\mathrm{作}\mathrm{次}\mathrm{数}bin[hash]=最少操作次数$ 的形式进行存储。
• DP转移：只需要计算哈希转移 $dp[i]=\min (dp[i],dp[i-j]+bin[hash])dp[i]=\backslash min\; (dp[i],dp[i-j]+bin[hash])$。

问题

枚举哈希情况数过多。

• 考虑剪枝。注意到 abcd ijkl 与 abba xyyx 本质上是一样的，可以经过处理让他们的哈希值相同。

代码

做法1

#include <cstdio>
#include <iostream>
#include <cstring>
#define int long long
const int N	= 1e6+10;
const int INF	= 1e9;
using namespace std;

int arr[N];
int arr_tmp[10];
int dp_tmp[100][100];
void DFS(int cur,int len,int lim)
{
	if(cur < len+1)
	{
		for (int i=1; i<=lim+1; i++)
		{
			arr_tmp[cur] = i;
			DFS(cur+1, len, max(i,lim));
		}
		return;
	}
	
	int T[5]={0};
	
	int minn = INF;
	
	for (int p=1; p<=7; p++)
	{
		for (int q=1; q<=7; q++)
		{
			T[1] = T[4] = p;
			T[2] = T[3] = q;
			
			for (int i=0; i<=len; i++)
			{
				for (int j=0; j<=4; j++)
				{
					dp_tmp[i][j] = INF;
				}
			}
			
			for (int i=0; i<=7; i++)
			{
				dp_tmp[i][0] = i;
			}
			for (int i=0; i<=4; i++)
			{
				dp_tmp[0][i] = i;
			}
			
			for (int i=1; i<=len; i++)
			{
				for (int j=1; j<=4; j++)
				{
					dp_tmp[i][j] = min(dp_tmp[i-1][j]+1, dp_tmp[i][j-1]+1);
					dp_tmp[i][j] = min(dp_tmp[i][j], dp_tmp[i-1][j-1] + (arr_tmp[i] != T[j]) );
				}
			}
			
			minn = min(minn, dp_tmp[len][4]);
		}
	}
	
	int hash=0;
	for (int i=1; i<=len; i++)
	{
		hash = hash * 8 + arr_tmp[i];
	}
	
	arr[hash] = minn;
}

void Init()
{
	for (int i=1; i<=7; i++)
	{
		DFS(1, i, 0);
	}
}

char str[N];
int dp[N];
int n;

void Sol()
{
	for (int i=0; i<=n; i++)
	{
		dp[i] = INF;
	}
	dp[0] = 0;
	
	for (int i=0; i<n; i++)
	{
		dp[i+1] = min(dp[i+1],dp[i]+1);
		
		int prei[27]={0};
		memset(prei, 0, sizeof(prei));
		int cnt=0;
		int hash=0;
		
		for (int j=1; j<=7 && i+j<=n; j++)
		{
			int ch = str[i+j]-'a'+1;
			if(!prei[ch])
				prei[ch] = ++cnt;
			
			hash = hash * 8 + prei[ch];
			
			dp[i+j] = min(dp[i+j], dp[i] + arr[hash]);
			
		}
	}
	
	printf("%lld\n",dp[n]);
}

signed main()
{
	Init();
	
	int tt;
	scanf("%lld",&tt);
	
	while(tt--)
	{
		scanf("%s",str+1);
		n=strlen(str+1);
		Sol();
	}
	
	return 0;
}

做法2

#include <cstdio>
#include <iostream>
#include <cstring>
#define int long long
const int N		= 1e6+10;
const int INF	= 1e9;
using namespace std;

int arr[N];
int arr_tmp[10];
int dp_tmp[100][100];
void DFS(int cur,int len,int lim)
{
	if(cur < len+1)
	{
		for (int i=1; i<=lim+1; i++)
		{
			arr_tmp[cur] = i;
			DFS(cur+1, len, max(i,lim));
		}
		return;
	}
	
	int T[5]={0};
	
	int minn = INF;
	
	for (int p=1; p<=7; p++)
	{
		for (int q=1; q<=7; q++)
		{
			T[1] = T[4] = p;
			T[2] = T[3] = q;
			
			for (int i=0; i<=len; i++)
			{
				for (int j=0; j<=4; j++)
				{
					dp_tmp[i][j] = INF;
				}
			}
			
			for (int i=0; i<=7; i++)
			{
				dp_tmp[i][0] = i;
			}
			for (int i=0; i<=4; i++)
			{
				dp_tmp[0][i] = i;
			}
			
			for (int i=1; i<=len; i++)
			{
				for (int j=1; j<=4; j++)
				{
					dp_tmp[i][j] = min(dp_tmp[i-1][j]+1, dp_tmp[i][j-1]+1);
					dp_tmp[i][j] = min(dp_tmp[i][j], dp_tmp[i-1][j-1] + (arr_tmp[i] != T[j]) );
				}
			}
			minn = min(minn, min(dp_tmp[len][4],dp_tmp[len][0]) );
		}
	}
	
	int hash=0;
	for (int i=1; i<=len; i++)
	{
		hash = hash * 8 + arr_tmp[i];
	}
	
	arr[hash] = minn;
}

void Init()
{
	for (int i=1; i<=7; i++)
	{
		DFS(1, i, 0);
	}
}

char str[N];
int dp[N];
int n;

void Sol()
{
	for (int i=0; i<=n; i++)
	{
		dp[i] = INF;
	}
	dp[0] = 0;
	
	for (int i=0; i<n; i++)
	{
		int prei[27]={0};
		memset(prei, 0, sizeof(prei));
		int cnt=0;
		int hash=0;
		
		for (int j=1; j<=7 && i+j<=n; j++)
		{
			int ch = str[i+j]-'a'+1;
			if(!prei[ch])
				prei[ch] = ++cnt;
			
			hash = hash * 8 + prei[ch];
			
			dp[i+j] = min(dp[i+j], dp[i] + arr[hash]);
			
		}
	}
	
	printf("%lld\n",dp[n]);
}

signed main()
{
	Init();
	
	int tt;
	scanf("%lld",&tt);
	
	while(tt--)
	{
		scanf("%s",str+1);
		n=strlen(str+1);
		Sol();
	}
	
	return 0;
}