统计单词个数80pts
查看原帖
统计单词个数80pts
817668
Hukaidi8566楼主2023/10/25 13:59

第4个和第9个测试点没有过,不知道怎么回事

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

int p,k;
char a[201];int ax;
int s;
char b[7][201];int bx[7],use[7];

int sum[201][201];
int f[201][201];
int dx[201][41];

int dfs(int,int);

int main()
{
	scanf("%d%d\n",&p,&k);
	for(int i=0;i<p;i++)
	{
		for(int j=1;j<=20;j++) scanf("%c",&a[i*20+j]);
		scanf("\n");
	}
	ax=p*20;
	scanf("%d",&s);
	for(int i=1;i<=s;i++)
	{
		scanf("%s",b[i]+1);
		bx[i]=strlen(b[i]+1);
		use[i]=1;
	}
	/*printf("a[]=\n");
	for(int i=1;i<=ax;i++) printf("%c",a[i]);
	printf("\n");*/
	
	for(int i=1;i<=s;i++)
	{
		for(int j=1;j<=s;j++)
		{
			if(i==j) continue;
			
			if(bx[i]>=bx[j])
			{
				if(use[i]==0) continue;
				
				int fx=0;
				for(int xk=1;xk<=bx[j];xk++)
				{
					if(b[i][xk]!=b[j][xk])
					{
						fx=1;
						break;
					}
				}
				
				if(fx==0) use[i]=0;
				//如果b[j]是b[i]的前缀,就忽略b[i],use[i]变为0 
			}
		}
	}
	/*printf("use[]=\n");
	for(int i=1;i<=s;i++) printf("%d ",use[i]);
	printf("\n");*/
	
	for(int i=1;i<=s;i++)
	{
		if(use[i]==0) continue;
		
		for(int j=0;j<=ax-bx[i];j++)
		{
			int fx=1;
			for(int xk=1;xk<=bx[i];xk++)
			{
				if(a[j+xk]!=b[i][xk])
				{
					fx=0;
					break;
				}
			}
			if(fx==1)
			{
				sum[j+1][j+bx[i]]=1;
				//记录有一个从 j+1 到 j+bx[i] 的满足条件的单词 
			}
		}
	}
	
	for(int i=1;i<=ax-1;i++)
	{
		for(int j=i+1;j<=ax;j++)
		{
			if(sum[i][j-1]==1)
			{
				sum[i][j]=1;
				//sum[i][j]表示以第i个为开始,到第j个及以内是否有单词 
			}
		}
	}
	for(int i=1;i<=ax;i++)
	{
		for(int j=i;j<=ax;j++)
		{
			if(sum[i][j]==1) f[i][j]=1;
		}
	}
	
	/*printf("sum[][]=\n");
	for(int i=1;i<=ax;i++){
		for(int j=1;j<=ax;j++) printf("%d ",sum[i][j]);
		printf("\n");
	}*/
	
	for(int cha=0;cha<ax;cha++)
	{
		for(int left=1;left+cha<=ax;left++)
		{
			int right=left+cha;
			f[left][right]=max(f[left][right],f[left+1][right]+sum[left][right]);
			//f[left][right]表示一整块从left到right的单词个数 
		}
	}
	/*printf("f[][]=\n");
	for(int i=1;i<=ax;i++){
		for(int j=1;j<=ax;j++) printf("%d ",f[i][j]);
		printf("\n");
	}*/
	
	for(int i=0;i<201;i++)
	{
		for(int j=0;j<41;j++)
		{
			dx[i][j]=-1;
		}
	}
	int ans=dfs(1,k);//记忆化搜索求解 
	printf("%d",ans);
	
	return 0;
}
int dfs(int left,int kk)
{
	//dfs(left,kk)或dx[left][kk]表示从left到ax分成kk段的最多单词个数 
	if(dx[left][kk]!=-1) return dx[left][kk];
	if(kk==1)
	{
		dx[left][kk]=f[left][ax];
		return f[left][ax];
	}
	
	int res=0;
	for(int lr=left;lr+kk-1<=ax;lr++)
	{
		res=max(res,f[left][lr]+dfs(lr+1,kk-1));
	}
	dx[left][kk]=res;
	return res;
}
2023/10/25 13:59
加载中...