위키오-엘리베이터-보급 일등-구분 dp-1040: 단어 개수 통계

출력 설명 Output Description

샘플 Sample Input 입력

샘플 출력 Sample Output

데이터 범위 및 프롬프트 Data Size & Hint

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

int len[210],dp[210][210];
string sen;

int mmin(int a,int b)
{
    if(a<0) return b;
    if(b<0) return a;
    return (a<b)?a:b;
}

int mmax(int a,int b)
{
    return (a>b)?a:b;
}

int fun(int pos,int k)
{
    if(pos<0 || k<=0) return 0;
    if(dp[pos][k]>0) return dp[pos][k];
    
    int endcnt[210],cnt = 0;
    memset(endcnt,0,sizeof(endcnt));
    
    for(int i=pos; i<=sen.length()-k; i++)
    {
        if(len[i]>0)
            endcnt[i+len[i]-1]++;
        cnt += endcnt[i];
        dp[pos][k] = mmax(dp[pos][k],cnt+fun(i+1,k-1));
    }
    return dp[pos][k];
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        memset(len,-1,sizeof(len));
        memset(dp,0,sizeof(dp));
        
        int p,k;
        cin>>p>>k;
        string tmp;
        while(p--)
        {
            cin>>tmp;
            sen += tmp;
        }
        
        int s;
        cin>>s;
        while(s--)
        {
            string word;
            cin>>word;
            for(int i=0; i<=sen.length()-word.length(); i++)
            {
                string sub(sen.substr(i,word.length()));
                if(word == sub)
                    len[i] = mmin(len[i],word.length());
            }
        }
        cout<<fun(0,k)<<endl;
    }
}