求条,玄3关,
查看原帖
求条,玄3关,
889917
limingyuan333楼主2024/8/7 22:09

调了一晚上,要红温了 a[2][1]值大于0??? 不知道怎么更新到的

#include<bits/stdc++.h>
#define int long long
using namespace std;
int pp,k;
unsigned int b[200010];
const int base=131,mod=194910017;
char c[2010];
int a[210][110];
int dp[210][210];
int le[2010];
unsigned int hash1[200010];
unsigned int mp[200010];
unsigned int get(int l,int r){
	return hash1[r]-hash1[l-1]*b[r-l+1];
}
bool get_hash(int l,int r){
	for(int i=1;i<=pp;i++){
		if(get(l,min(l+le[i]-1,r))==mp[i]){
			if(l==109&&r==1)	cout<<mp[i]<<" ";
			return 1;
		}
	}
	return 0;
}
unsigned int hsh(string s){
	unsigned int ans=0;
	int len=s.size();
	for(int i=1;i<=len;i++){
		ans=(ans*base+s[i-1]);
	//	cout<<ans<<' ';
	}
	return ans;
}
signed main(){
	int n;
	cin>>n>>k;
	int len=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=20;j++){
			cin>>c[++len];
		}
	}
	b[0]=1;
	for(int i=1;i<=len;i++){
		b[i]=(b[i-1]*base);
		//cout<<c[i]<<' ';
		hash1[i]=(hash1[i-1]*base+c[i]);
	
	//	cout<<hash1[i]<<' '
;	}
	cin>>pp;
	string s;
	for(int i=1;i<=pp;i++){
		cin>>s;	
		le[i]=s.size();
		mp[i]=hsh(s);
	//	cout<<mp[i]<<' '<<le[i]<<'\n';
	}
	memset(a,0,sizeof(a));
	for(int i=len;i>=1;i--){
		for(int j=i;j>=1;j--){
			a[j][i]=a[j+1][i];
	//		cout<<a[j][1]<<" ";
			if(get_hash(j,i)){
			
				//	cout<<1;
					a[j][i]++;}
//			if(i==1)
//				cout<<a[j][i]<<' ';
			
		}
	}
//	cout<<get_hash(109,1)<<' ';
//	for(int i=1;i<=len;i++){
//		cout<<a[i][1]<<" ";
//	}
	for(int i=1;i<=len;i++){
		dp[i][1]=a[1][i];
	//	cout<<a[1][i]<<" ";
		for(int j=2;j<=k;j++){
			for(int p=1;p<i;p++){
				if(dp[p][j-1])
					dp[i][j]=max(dp[i][j],dp[p][j-1]+a[p+1][i]);
			}
		}
	}
	cout<<dp[len][k];
	return 0;
}
2024/8/7 22:09
加载中...