D题wa一个点求调
  • 板块学术版
  • 楼主mayike
  • 当前回复5
  • 已保存回复5
  • 发布时间2024/3/9 21:42
  • 上次更新2024/3/9 23:05:16
查看原帖
D题wa一个点求调
1039406
mayike楼主2024/3/9 21:42

dp

#include<bits/stdc++.h>
using namespace std;
string T,s[101][11],c[101];
int n,a[101],m,f[101];
int main(){
	cin>>T>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		for(int j=1;j<=a[i];j++)cin>>s[i][j];
	}m=T.size(),T=" "+T,f[0]=0,c[0]="";
	for(int i=1;i<=m;i++)c[i]=c[i-1]+T[i];
	for(int i=1;i<=m;i++)f[i]=2e9;
		for(int j=1;j<=n;j++)
			for(int k=1;k<=a[j];k++)
				for(int i=m;i;i--)
				    if(i>=s[j][k].size()&&f[i-s[j][k].size()]!=2e9&&c[i-s[j][k].size()]+s[j][k]==c[i])f[i]=min(f[i],f[i-s[j][k].size()]+1);
	if(f[m]==2e9)cout<<-1<<"\n";
   else cout<<f[m]<<"\n";
   return 0;
}
2024/3/9 21:42
加载中...