Class assignment (6) - 575. Word division (word)

Catalog

Description

Format

Input

Output

Samples

input data 1

Output data 1

Hint

Limitation

Answer key ：

Program

Description

There is a long string of lowercase letters . To facilitate the analysis of this string , It needs to be divided into several parts , Each part is called a word . For the purpose of reducing the amount of analysis , We want to divide as few words as possible . You are here to complete this division .

Format

Input

The first  1  That's ok , A string .（ The length of the string does not exceed  100）

The first  2 Line an integer n, Indicates the number of words .(n<=100）

The first 3∼n+2  That's ok , List one word per line .

Output

An integer , Represents the minimum number of words that a string can be divided into .

Samples

input data 1

realityour
5
real
reality
it
your
our

Output data 1

2

Hint

The original string can be split into real+it+your or reality+our, because reality+our Just two parts , Therefore, the optimal solution is 2, Also note , Each word in the word list can be used repeatedly , It can also be done without

Limitation

1s, 1024KiB for each test case.

Answer key ：

It's the deformed knapsack problem , after complex After judgment and loop traversal, find the smallest solution , State transition equation ：

dp[k]=min(dp[k],dp[k-a[j].size()]+1);// State transition equation  

Program ：

#include<bits/stdc++.h>
using namespace std;
string a[110],s;
int n,len,len1,dp[110];
int main(){
    cin>>s>>n;
    len=s.size();// The length of the string  
    for(int i=0;i<n;i++)
        cin>>a[i];
    memset(dp,0x3f,sizeof(dp));// Set it to infinity  
    dp[0]=0;
    for(int i=0,k;i<len;i++,k=i+1;/* Traversed position */)
        for(int j=0;j<n;j++len1=a[j].size();/* The length of the word */) 
            if(len1<=k)// Judge whether the length of this word is less than the current traversal position  
                if(s.substr(k-len1,len1)==a[j])// Determine whether the part of the string is the same as the currently traversed word  
                    dp[k]=min(dp[k],dp[k-a[j].size()]+1);// State transition equation  
    cout<<dp[len];
    return 0;
}