1 条题解

  • 2
    @ 2022-11-5 12:00:45
    #include<bits/stdc++.h>
    using namespace std;
    int n,f[110];
    string s,a[110];
    //动态转移方程:f[i]=min(f[i],f[i-a[j].size()]+1) 
    bool check(int i,int j){
    	for(int k=a[j].size()-1,b=i;k>=0;k--,b--)
    		if(s[b]!=a[j][k])return false;
    	return true;
    }
    int main() {
    	memset(f,1,sizeof(f));
    	f[0]=0;//特殊赋值 
        cin>>s>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=0;i<s.size();i++)
        	for(int j=1;j<=n;j++)
        		if(a[j].size()<=i+1)if(check(i,j))f[i+1]=min(f[i+1],f[i+1-a[j].size()]+1);
    	cout<<f[s.size()];
    }
    
    

    信息

    ID
    1526
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    18
    已通过
    15
    上传者