[SCOI2007]压缩

2024-04-03 15:03:22

V.[SCOI2007]压缩

这种DP状态需要考虑到各种状态的题最讨厌了……

思路1.设\(f[i][j]\)表示将区间\([i,j]\)里面所有东西压一起的最小代价

有两种转移：

砍成两段拼一起
样例里面这种方法，MaRR=aaaa 这种倍增法

然后我就写出了这样的代码：

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
char s[110];
int n,f[110][110];
ull sd1=998244353,sd2=666623333,pov1[2001000],pov2[2001000];
struct HASH{
	ull val1,val2;
	int len;
	HASH(){
		val1=val2=0ull;
		len=0;
	}
	HASH(char ip){
		val1=val2=ip;
		len=1;
	}
	friend HASH operator +(const HASH &x,const HASH &y){
		HASH z;
		z.val1=x.val1*pov1[y.len]+y.val1;
		z.val2=x.val2*pov2[y.len]+y.val2;
		z.len=x.len+y.len;
		return z;
	}
	friend HASH operator -(const HASH &x,const HASH &y){
		HASH z;
		z.val1=x.val1-y.val1*pov1[x.len-y.len];
		z.val2=x.val2-y.val2*pov2[x.len-y.len];
		z.len=x.len-y.len;
		return z;
	}
	friend bool operator ==(const HASH &x,const HASH &y){
		if(x.len!=y.len)return false;
		if(x.val1!=y.val1)return false;
		if(x.val2!=y.val2)return false;
		return true;
	}
	friend bool operator !=(const HASH &x,const HASH &y){
		return !(x==y);
	}
}hs[110];
bool che(int ip){
	return ip==(ip&-ip);
}
int main(){
	scanf("%s",s+1),memset(f,0x3f3f3f3f,sizeof(f)),n=strlen(s+1);
	pov1[0]=pov2[0]=1;
	for(int i=1;i<=n;i++)pov1[i]=pov1[i-1]*sd1,pov2[i]=pov2[i-1]*sd2;
	for(int i=1;i<=n;i++)hs[i]=hs[i-1]+HASH(s[i]),f[i][i]=1;
	for(int l=2;l<=n;l++){
		for(int i=1,j=i+l-1;j<=n;i++,j++){
			for(int k=i;k<j;k++)f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
			for(int k=1;k<l;k++){
				if(l%k)continue;
				if((hs[j]-hs[i+k-1])!=(hs[j-k]-hs[i-1]))continue;
				if(!che(l/k))continue;
//				printf("%d %d %d\n",i,j,l/k);
				f[i][j]=min(f[i][j],f[i][i+k-1]+__builtin_ctz(l/k)+(i!=1));
			}
		}
	}
//	for(int l=1;l<=n;l++){for(int i=1,j=i+l-1;j<=n;i++,j++)printf("%d ",f[i][j]);puts("");}
	printf("%d\n",f[1][n]);
	return 0;
}

一交，WA，\(40\%\)。

怎么回事？

我费尽千辛万苦，找到一组hack数据：

xabababababab

按照我之前的这种压法，会压出来xMMabRabR这种东西。因为这时区间DP，按照我之前的思路，是按照括号的顺序压的：

x(M(MabR)abR)

因此，相同的左端点，如果已经有了一个M，就不用重复有M了。

我们设一个新状态\(f[i][j][0/1]\)表示：将区间\([i,j]\)压一起，左端点有无M的状态是\([0/1]\)。

然后写出来这样的东西：

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
char s[110];
int n,f[110][110][2];
ull sd1=998244353,sd2=666623333,pov1[2001000],pov2[2001000];
struct HASH{
	ull val1,val2;
	int len;
	HASH(){
		val1=val2=0ull;
		len=0;
	}
	HASH(char ip){
		val1=val2=ip;
		len=1;
	}
	friend HASH operator +(const HASH &x,const HASH &y){
		HASH z;
		z.val1=x.val1*pov1[y.len]+y.val1;
		z.val2=x.val2*pov2[y.len]+y.val2;
		z.len=x.len+y.len;
		return z;
	}
	friend HASH operator -(const HASH &x,const HASH &y){
		HASH z;
		z.val1=x.val1-y.val1*pov1[x.len-y.len];
		z.val2=x.val2-y.val2*pov2[x.len-y.len];
		z.len=x.len-y.len;
		return z;
	}
	friend bool operator ==(const HASH &x,const HASH &y){
		if(x.len!=y.len)return false;
		if(x.val1!=y.val1)return false;
		if(x.val2!=y.val2)return false;
		return true;
	}
	friend bool operator !=(const HASH &x,const HASH &y){
		return !(x==y);
	}
}hs[110];
bool che(int ip){
	return ip==(ip&-ip);
}
int main(){
	scanf("%s",s+1),memset(f,0x3f3f3f3f,sizeof(f)),n=strlen(s+1);
	pov1[0]=pov2[0]=1;
	for(int i=1;i<=n;i++)pov1[i]=pov1[i-1]*sd1,pov2[i]=pov2[i-1]*sd2;
	for(int i=1;i<=n;i++){
		hs[i]=hs[i-1]+HASH(s[i]);
		f[i][i][0]=1;
		f[i][i][1]=1+(i!=1);
	}
	for(int l=2;l<=n;l++){
		for(int i=1,j=i+l-1;j<=n;i++,j++){
			for(int k=i;k<j;k++)f[i][j][0]=min(f[i][j][0],f[i][k][0]+min(f[k+1][j][0],f[k+1][j][1])),f[i][j][1]=min(f[i][j][1],f[i][k][1]+min(f[k+1][j][0],f[k+1][j][1]));
			for(int k=1;k<l;k++){
				if(l%k)continue;
				if((hs[j]-hs[i+k-1])!=(hs[j-k]-hs[i-1]))continue;
				if(!che(l/k))continue;
//				printf("%d %d %d\n",i,j,l/k);
				f[i][j][1]=min(f[i][j][1],min(f[i][i+k-1][0]+1,f[i][i+k-1][1])+__builtin_ctz(l/k));
			}
		}
	}
//	for(int l=1;l<=n;l++){for(int i=1,j=i+l-1;j<=n;i++,j++)printf("%d ",f[i][j]);puts("");}
	printf("%d\n",f[1][n][1]);
	return 0;
}
//xabababababab

一交，WA，\(70\%\)。

然后我想了想，那种倍增的合并法也可以并入（左端点已经有了M）的情形。

然后我改成了这样的代码（这种情形实际上哈希都没必要了）

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
char s[110];
int n,f[110][110][2];
ull sd1=998244353,sd2=666623333,pov1[2001000],pov2[2001000];
struct HASH{
	ull val1,val2;
	int len;
	HASH(){
		val1=val2=0ull;
		len=0;
	}
	HASH(char ip){
		val1=val2=ip;
		len=1;
	}
	friend HASH operator +(const HASH &x,const HASH &y){
		HASH z;
		z.val1=x.val1*pov1[y.len]+y.val1;
		z.val2=x.val2*pov2[y.len]+y.val2;
		z.len=x.len+y.len;
		return z;
	}
	friend HASH operator -(const HASH &x,const HASH &y){
		HASH z;
		z.val1=x.val1-y.val1*pov1[x.len-y.len];
		z.val2=x.val2-y.val2*pov2[x.len-y.len];
		z.len=x.len-y.len;
		return z;
	}
	friend bool operator ==(const HASH &x,const HASH &y){
		if(x.len!=y.len)return false;
		if(x.val1!=y.val1)return false;
		if(x.val2!=y.val2)return false;
		return true;
	}
	friend bool operator !=(const HASH &x,const HASH &y){
		return !(x==y);
	}
}hs[110];
int main(){
	scanf("%s",s+1),memset(f,0x3f3f3f3f,sizeof(f)),n=strlen(s+1);
	pov1[0]=pov2[0]=1;
	for(int i=1;i<=n;i++)pov1[i]=pov1[i-1]*sd1,pov2[i]=pov2[i-1]*sd2;
	for(int i=1;i<=n;i++){
		hs[i]=hs[i-1]+HASH(s[i]);
		f[i][i][0]=1;
		f[i][i][1]=1+(i!=1);
	}
	for(int l=2;l<=n;l++){
		for(int i=1,j=i+l-1;j<=n;i++,j++){
			for(int k=i;k<j;k++)f[i][j][0]=min(f[i][j][0],f[i][k][0]+min(f[k+1][j][0],f[k+1][j][1])),f[i][j][1]=min(f[i][j][1],f[i][k][1]+min(f[k+1][j][0],f[k+1][j][1]));
			if(l&1)continue;
			int k=l>>1;
			if((hs[j]-hs[i+k-1])!=(hs[j-k]-hs[i-1]))continue;
			f[i][j][1]=min(f[i][j][1],min(f[i][i+k-1][0]+1,f[i][i+k-1][1])+1);
		}
	}
//	for(int l=1;l<=n;l++){for(int i=1,j=i+l-1;j<=n;i++,j++)printf("%d ",f[i][j]);puts("");}
	printf("%d\n",f[1][n][1]);
	return 0;
}
//xabababababab
//xabcabcxabcabc

一交，WA，还是\(70\%\)。

我费劲千辛万苦，终于找到另一组hack数据：

xabcabcxabcabc

按照我之前的思路，会压出来这样的东西：

xMabcRR

因为我的程序是这样考虑的：

x(MabcR)R，根本没有考虑内部的情况

因此还要额外再加一维，表示该串内部有无M：

我们现在得到的是状态\(f[i][j][0/1][0/1]\)。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
char s[110];
int n,f[110][110][2][2];
ull sd1=998244353,sd2=666623333,pov1[2001000],pov2[2001000];
struct HASH{
	ull val1,val2;
	int len;
	HASH(){
		val1=val2=0ull;
		len=0;
	}
	HASH(char ip){
		val1=val2=ip;
		len=1;
	}
	friend HASH operator +(const HASH &x,const HASH &y){
		HASH z;
		z.val1=x.val1*pov1[y.len]+y.val1;
		z.val2=x.val2*pov2[y.len]+y.val2;
		z.len=x.len+y.len;
		return z;
	}
	friend HASH operator -(const HASH &x,const HASH &y){
		HASH z;
		z.val1=x.val1-y.val1*pov1[x.len-y.len];
		z.val2=x.val2-y.val2*pov2[x.len-y.len];
		z.len=x.len-y.len;
		return z;
	}
	friend bool operator ==(const HASH &x,const HASH &y){
		if(x.len!=y.len)return false;
		if(x.val1!=y.val1)return false;
		if(x.val2!=y.val2)return false;
		return true;
	}
	friend bool operator !=(const HASH &x,const HASH &y){
		return !(x==y);
	}
}hs[110];
int main(){
	scanf("%s",s+1),memset(f,0x3f3f3f3f,sizeof(f)),n=strlen(s+1);
	pov1[0]=pov2[0]=1;
	for(int i=1;i<=n;i++)pov1[i]=pov1[i-1]*sd1,pov2[i]=pov2[i-1]*sd2;
	for(int i=1;i<=n;i++){
		hs[i]=hs[i-1]+HASH(s[i]);
		f[i][i][0][0]=1;
		f[i][i][1][0]=1+(i!=1);
	}
	for(int l=2;l<=n;l++){
		for(int i=1,j=i+l-1;j<=n;i++,j++){
			for(int k=i;k<j;k++){
				f[i][j][0][0]=min(f[i][j][0][0],f[i][k][0][0]+f[k+1][j][0][0]);
				f[i][j][1][0]=min(f[i][j][1][0],f[i][k][1][0]+f[k+1][j][0][0]);
				f[i][j][0][1]=min(f[i][j][0][1],min(f[i][k][0][1],f[i][k][0][0])+min(min(f[k+1][j][0][0],f[k+1][j][0][1]),min(f[k+1][j][1][0],f[k+1][j][1][1])));
				f[i][j][1][1]=min(f[i][j][1][1],min(f[i][k][1][1],f[i][k][1][0])+min(min(f[k+1][j][0][0],f[k+1][j][0][1]),min(f[k+1][j][1][0],f[k+1][j][1][1])));
			}
			if(l&1)continue;
			int k=l>>1;
			if((hs[j]-hs[i+k-1])!=(hs[j-k]-hs[i-1]))continue;
			f[i][j][1][0]=min(f[i][j][1][0],min(f[i][i+k-1][0][0]+1,f[i][i+k-1][1][0])+1);
		}
	}
//	for(int l=1;l<=n;l++){for(int i=1,j=i+l-1;j<=n;i++,j++)printf("%d ",f[i][j]);puts("");}
	printf("%d\n",min(f[1][n][1][0],f[1][n][1][1]));
	return 0;
}
//xabababababab
//xabcabcxabcabc

码农公寓

V.[SCOI2007]压缩

相关文章