숫자nullRQNOJ-302- 단어 개수 집계 - 영역 dp

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<stdlib.h>
#define INF_MAX 0x7fffffff
#define INF 999999
#define max3(a,b,c) (max(a,b)>c?max(a,b):c)
#define min3(a,b,c) (min(a,b)<c?min(a,b):c)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
struct node
{
    int u;
    int v;
    int w;
    bool friend operator < (node a, node b){
        return a.w < b.w;
    }
}edge[1001];
int gcd(int n,int m){if(n<m) swap(n,m);return n%m==0?m:gcd(m,n%m);}
int lcm(int n,int m){if(n<m) swap(n,m);return n/gcd(n,m)*m;}
char dic[10][201];
char str[201];
char  st[21];
int sum[201][201];
int s[201][201];
int p,k,ss;
int main()
{
    int i,j,n;
    scanf("%d%d%*c",&p,&k);
    for(i=0;i<p;i++)
    {
        gets(st);
        for(j=i*20;j<i*20+20;j++)
        {
            str[j]=st[j-i*20];
        }
    }
    n=p*20;
    scanf("%d%*c",&ss);
    for(i=0;i<ss;i++)
    {
        gets(dic[i]);
    }
    int mi,is,ks;
    for(i=0;i<n;i++)
    {
        mi=n;
        for(j=0;j<ss;j++)
        {
            if(str[i]==dic[j][0])
            {
                for(ks=0;ks<strlen(dic[j])&&(i+ks)<n;ks++)
                {
                    if(str[ks+i]!=dic[j][ks])break;
                }
                if(ks==strlen(dic[j]))mi=min(mi,i+ks-1);
            }

        }
        for(is=mi;is<n;is++)
        {
            s[i][is]=1;
        }
    }
    for(i=0;i<n;i++)
    sum[n-1][i]=s[n-1][i];
    for(i=n-2;i>=0;i--)
    {
        for(j=i;j<n;j++)
        {
            if(s[i][j]==1)sum[i][j]=sum[i+1][j]+1;
            else sum[i][j]=sum[i+1][j];
        }
    }
    int dp[10][201];
  /*  for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            printf("%2d ",sum[i][j]);
        }
        puts("");
    }*/
    for(i=0;i<n;i++)
    {
        dp[1][i]=sum[0][i];
    }
    for(i=2;i<=k;i++)
    {
        for(j=0;j<n;j++)
        {
            dp[i][j]=0;
            for(ks=i-2;ks<j;ks++)
            {
                dp[i][j]=max(dp[i][j],dp[i-1][ks]+sum[ks+1][j]);

            }
        }
    }
    cout<<dp[k][n-1]<<endl;
    return 0;
}