[GKOI 2021 提高组]抄写

抄写copy

题目大意

对于 \(26\) 个英文字母,每个英文字母对应一个权值,对于任意小写字母 \(ch\) ,我们称抄写它的花费为 \(cost_{ch}\)

当然,你有一种节约时间的方法,你可以花费时间 \(c\) ,将之前抄写的字符对称到另一边,即如下两种操作:

  • 操作一,在 \(s_m\) 后对称,即使得抄写进度变为 \(s_1s_2……s_ms_ms_{m-1}……s_k,1\leq k \leq m\)

  • 操作一,在 \(s_m\) 处对称,即使得抄写进度变为 \(s_1s_2……s_ms_{m-1}……s_k,1\leq k < m\)

现在给你一个长度为 \(n\) 的字符串,问你抄写它的最小花费。

分析

暴力解法

首先,这道题的 \(n^2\) 做法并不难想到,我们设 \(dp[i]\) 表示抄写前 \(i\) 个字符的最小花费,显然, \(dp[i]\) 有两种被更新的方式。

\[dp[i]=min(dp[i-1]+cost[s[i]-‘a‘+1],dp[k]+c) \]

很显然,这个 \(k\) 即我们的对称点,如果不加优化的话,我们只能通过枚举去找,且判断是否对称又是一维,这样我们的时间复杂度显然是不优秀的。

我们考虑在每个点的时候更新后面的点,就是以当前更新到的点作为题面中的 \(s_m\) ,左右两边同时向外判断,如果一直相同,就更新即可。

这样我们的时间复杂度能够达到 \(n^2\)

然后这题其实还有一点性质分,二分的做法很容易想到,这里就不赘述了。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,INF=1e10;
inline int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) w*=-1; ch=getchar(); }
	while(ch>=‘0‘&&ch<=‘9‘) s=s*10+ch-‘0‘,ch=getchar();
	return s*w;
}
int n,c;
int f[N],cost[N];
char s[N];
inline int find(int l,int r,char x)
{
	int res=-1;
	while(l<=r){
		int mid=(l+r)/2;
		if(s[mid]!=x) l=mid+1;
		else res=mid,r=mid-1;
	}
	return res;
}
//目测60分 
signed main()
{
//	freopen("copy.in","r",stdin);
//	freopen("copy.out","w",stdout);
	n=read(),c=read();
	for(register int i=1;i<=26;i++) cost[i]=read();
	for(register int i=1;i<=n;i++) s[i]=getchar();
	for(register int i=1;i<=n;i++) f[i]=INF;
	f[0]=0;
	if(n<=1000){ //40分 
		for(register int i=1;i<=n;i++){
			//cout<<i<<"\n";
			f[i]=min(f[i-1]+cost[s[i]-‘a‘+1],f[i]);
			int l=i,r=i+1;
			while(l>=1&&r<=n){ //操作1
				if(s[l]==s[r]){ //能够关于其对称 
					f[r]=min(f[r],f[i]+c);
					l--,r++;
				}
				else break;
			}
			l=i-1,r=i+1;
			while(l>=1&&r<=n){ //操作2 
				if(s[l]==s[r]){ //能够关于其对称 
					f[r]=min(f[r],f[i]+c);
					l--,r++;
				}
				else break;
			}
		}
		printf("%lld\n",f[n]);
	} 
	else{ //性质分20分
		for(register int i=1;i<=n;i++){
			//cout<<i<<"\n";
			int k=find(1,i-1,s[i]);
			if(k==-1) f[i]=f[i-1]+cost[s[i]-‘a‘+1];
			else{
				int mid=(i-k+1)/2;
				if((i-k+1)&1) mid+=1;
				f[i]=min(f[i-1]+cost[s[i]-‘a‘+1],f[k+mid-1]+c);
			}
		}
		printf("%lld\n",f[n]);
	}
	return 0;
}

正解(hash+二分+线段树)

这是一种 \(nlogn\) 的解法,扩展 \(kmp\)\(manacher\) 等算法也能做到。

想想怎么优化我们的过程,通过枚举去找到最大的边界然后一个一个更新,还是太暴力了。对于这种区间更新,线段树是比较显然的一种想法,但是我们如何在优秀的时间复杂度内找到回文半径。

我们可以把原来的字符串正着 \(hash\) 一遍,倒着 \(hash\) 一遍,在二分回文半径即可。

这样做的时间是 \(nlogn\)

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,INF=1e18;
inline int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) w*=-1; ch=getchar(); }
	while(ch>=‘0‘&&ch<=‘9‘) s=s*10+ch-‘0‘,ch=getchar();
	return s*w; 
}
int n,c;
int a[N],f[N],dp[N],tree[4*N]; //f[i]记录第i个点通过回文能够更新到的点的最远位置 
char s[N];
unsigned long long p[N],hash1[N],hash2[N];
inline void build(int k,int l,int r)
{
	if(l==r) { tree[k]=INF; return; }
	int mid=(l+r)/2;
	build(k*2,l,mid),build(k*2+1,mid+1,r);
	tree[k]=min(tree[k*2],tree[k*2+1]);
}
inline void change(int k,int l,int r,int x,int y,int v)
{
	if(l>y||r<x) return;
	if(l>=x&&r<=y) { tree[k]=min(tree[k],v); return; }
	int mid=(l+r)/2;
	change(k*2,l,mid,x,y,v),change(k*2+1,mid+1,r,x,y,v);
}
inline int ask(int k,int l,int r,int x)
{
	if(r<x||l>x) return INF;
	if(l==r) return tree[k];
	int mid=(l+r)/2;
	return min(tree[k],min(ask(k*2,l,mid,x),ask(k*2+1,mid+1,r,x)));
}
signed main()
{
	n=read(),c=read();
	for(register int i=1;i<=26;i++) a[i]=read();
	scanf("%s",s+1);
	p[0]=1;
	for(register int i=1;i<=n;i++){
		hash1[i]=hash1[i-1]*131+(s[i]-‘a‘+1);
		hash2[n-i+1]=hash2[n-i+2]*131+(s[n-i+1]-‘a‘+1);
		p[i]=p[i-1]*131;
	}
//	for(register int i=1;i<=n;i++) cout<<hash2[i]<<" ";
//	puts("");
	for(register int i=1;i<=n;i++){
		int l=0,r=min(i-1,n-i),res=-1;
		while(l<=r){ //奇数 
			int mid=(l+r)/2;
			if(hash1[i]-hash1[i-mid-1]*p[mid+1]==hash2[i]-hash2[i+mid+1]*p[mid+1]) res=mid,l=mid+1;
			else r=mid-1;
		}
		if(res!=-1) f[i]=max(f[i],i+res);
		l=0,r=min(i-1,n-i-1),res=-1;
		while(l<=r){ //偶数 
			int mid=(l+r)/2;
			if(hash1[i]-hash1[i-mid-1]*p[mid+1]==hash2[i+1]-hash2[i+mid+2]*p[mid+1]) res=mid,l=mid+1;
			else r=mid-1;
		}
		if(res!=-1) f[i]=max(f[i],i+res+1);
	}
	build(1,1,n);
	for(register int i=1;i<=n;i++){
		dp[i]=min(dp[i-1]+a[s[i]-‘a‘+1],ask(1,1,n,i));
		if(i+1>f[i]) continue;
		else change(1,1,n,i+1,f[i],dp[i]+c);
	}
	printf("%lld\n",dp[n]);
	return 0;
}

[GKOI 2021 提高组]抄写

上一篇:从文件read一个字节所发生的磁盘IO


下一篇:辗转相除法的一种理解(类比法)