ABC D 求调
  • 板块学术版
  • 楼主Hughpig
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/3/9 21:43
  • 上次更新2024/3/9 23:16:32
查看原帖
ABC D 求调
646208
Hughpig楼主2024/3/9 21:43

就 WA\text{WA} 一个点/ll

/*
*Author: Hughpig
*made in China
*/

#include<bits/stdc++.h>
using namespace std;
#define ll long long
string t,tmp;
int n,a[107],f[107][1007];
vector<string> s[107];

int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
	cin>>t>>n;
	t=" "+t;
	memset(f,0x3f,sizeof(f));
	for(int i=0;i<=n;i++)f[i][0]=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s[i].push_back("");
		for(int j=1;j<=a[i];++j){
			cin>>tmp;
			s[i].push_back(tmp);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=a[i];++j){
			for(int pos=1;pos<t.size();++pos){
				if(t.substr(pos,s[i][j].size())==s[i][j]){
					if(pos==1)f[i][s[i][j].size()]=1;
					else f[i][pos+s[i][j].size()-1]=min(f[i-1][pos+s[i][j].size()-1],f[i-1][pos-1]+1);
				}
				f[i][pos]=min(f[i][pos],f[i-1][pos]);
			}
		}
	}
	if(f[n][t.size()-1]<=1000)cout<<f[n][t.size()-1];
	else cout<<-1;
	return 0;
}
2024/3/9 21:43
加载中...