wikioi1040 단어 개수 통계

제목 설명Description

길이가 200을 넘지 않는 소문자 영문 자모로 구성된 자모열을 제시한다.이 알파벳을 k부로 나누기를 요구합니다. (단어는 6개를 넘지 않는 사전에서 나온다. 최대 개수를 출력해야 합니다.

설명 입력 Input Description

첫 번째 행위는 하나의 정수(0각 그룹의 첫 줄에 두 개의 정수(p,k)p가 문자열의 줄 수를 나타낸다.k는 k부분으로 나뉘는 것을 나타낸다.다음 p 줄은 줄마다 20자입니다.그 다음에 사전의 단어 개수를 나타내는 정수 s가 있다.(1<=s<=6) 다음 s줄은 줄마다 단어가 하나씩 있습니다.

출력 설명 Output Description

줄마다 정수가 하나씩 있고 각 그룹의 테스트 데이터에 대응하는 상응하는 결과이다.

샘플 Sample Input 입력

1 1 3 thisisabookyouareaoh 4 is a ok sab

샘플 출력 Sample Output

7

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

this/isabookyoua/reaoh
방금 이 제목을 보고 막막해서 손을 대지 못했는데 갑자기 반짝이는 돌파구가 보였다.
제목에서this는this와is를 포함하지만th는 포함하지 않는다. 이것은 바로 한 줄에
시작점이 정해진 단어는 한 번만 쓸 수 있고, 다른 단어를 구성할 수 있어도 그는 한 번 쓴다.꿰미:thisa
사전:this is th
열에는 this is th라는 세 단어가 있지만, this와th에 대해서는 한 번만 사용하고,
즉, 단어를 구성하는 시작점을 일일이 열거하면 그 시작점의 열에 그 시작점으로 시작할 수 있는 단어가 포함되면
그러면 이 열에 한 단어가 더 포함되어 있다는 것을 설명한다.
이렇게 하면 다음과 같은 결과를 얻을 수 있다.
열거의 기점 결론:
t 1개 이상 포함
h 최소 1개 포함
i 최소 2개
s 최소 2개 포함
a 2개 이상 포함
여기까지만 생각하면 갈피를 잡을 수 있다.
제목에서 k개의 부분을 직렬로 나누어야 한다. 즉, 한 점에서 끊은 후의 단어가 반드시 구성될 수 있는 것은 아니다.
예를 들어 상례에서 세 부분으로 나뉘어야 하는데 합리적인 한 부분은 기껏해야 세 개의 자모가 있기 때문에this라는 단어는 구성할 수 없다.
다섯 부분으로 나누면 단어 하나도 구성할 수 없다.
이렇게 하면 위에 변동을 해야 한다. 위에 있는 것은 시작점만 컨트롤하고
그리고 제목에서 종점을 제한해야 한다. 몇 개의 부분을 나눈 후에 각 부분의 종점이 다르면 구성할 수 있는 단어가 다르다.
이렇게 되면 다시 결승점을 매거해야 한다.
2차원 그룹sum[i,j]을 설계하여 i부터 j까지의 열에 포함된 단어의 개수를 통계합니다.
상태 전환 방정식:
sum[i+1, j]+1(s[i, j]에는 s[i]로 시작하는 단어가 포함됨)
sum[i,j]=sum[i+1,j](위와 반대)
주: (1) 여기서 문자를 매거하는 시작점의 순서는 끝에서 끝까지입니다.
(2) 어떤 사람은 위에서 이번에도 동태적인 기획이라고 생각하지만 나는 더욱 정확하게 말하면 점차적으로 추진하는 것이라고 생각한다.
모든sum를 구하는 데는 아직 한 발자국도 모자란다. 바로 서로 다른 구분 방법은 분명히 결과가 다르다.
그러나 해답을 구하는 문제에 대해 우리는 이렇게 원문제를 자문제로 분해할 수 있다.
한 꿰미를 k부분으로 나누는 가장 많은 단어 개수를 구하는 것은 꿰미의 마지막 부분을 먼저 나누는 것으로 볼 수 있다.
앞부분을 k-1부분으로 분해하고,
분명히 결정은 앞의 k-1부분의 단어 + 마지막 부분의 단어가 가장 많은 구분 방법을 찾는 것이다.
분명히 이 문제는 가장 최적화된 원리를 만족시킨다. 그러면 후효성이 없는 것에 만족하는가?
한 꿰미가 마지막 부분을 분해하는 데 있어서 앞의 부분은 분리된 부분과 전혀 관련이 없다.
다시 말하면 매번 분해할 때마다 열을 더욱 작게 분해하는데, 이 작은 열을 분해하는 데 이 작은 열에 속하지 않는 원소를 쓰지 않는다.
이것은 무후효성을 만족시킨다.
구체적 해결 절차:
상태opt[i,j]를 설계하여 1부터 j까지의 직렬을 i분으로 나누면 가장 많은 단어를 얻을 수 있는 개수를 나타낸다.
결정은 매거 분할점으로 현재의 이런 분할 방법이 가장 많은 단어를 얻을 수 있도록 하는 것이다.
상태 이동 방정식:opt[i, j]=max(opt[i-1, t]+sum[t+1, j])(i
경계 조건:opt[1,i]=sum[1,i](0
시간 복잡도: 상태 수 O(N2)* 결정 수 O(N)=O(N3), 공간 복잡도: O(N2).

#include 
#include 

int word[201][201], dp[201][201][41];
char c[21], w[6][10], c0[201], c1[201];
int d, p, k, s, max, le[6], len;

int main()
{
	int i, j, l, m, yes, x, st;
 	scanf("%d", &d);
 	while(d--)
	{
		scanf("%d%d", &p, &k);
  		for(j = 0; j < p; j++)
		{
   			scanf("%s", c);
   			if(j == 0)	strcpy(c0, c);
   			else		strcat(c0, c);
  		}
  		len = strlen(c0);
  		scanf("%d", &s);
  		for(j = 0; j < s; j++)
		{
   			scanf("%s", w[j]);
   			le[j] = strlen(w[j]);
  		}
  		for(i = 0; i < len; i++)
   			for(j = 0; j < len; j++)
    			word[i][j] = 0; 
//************************************************************************
/*   j :c0[j-1]  i :c0[i-1]        word[j][i] */
  		for(i = len-1; i >= 0; i--) 
   			for(j = len-1; j >= 0; j--)
			{
    			for(l = 0; l < s; l++)
				{
     				yes = 0;
     				if(c0[j] == w[l][0] && le[l] <= i-j+1)
					{
      					yes = 1; 
      					for(m = 0; m < le[l]; m++)
       						if(c0[j+m] != w[l][m])
       						{
						   		yes = 0; 
						   		break; 
							}
     				}
     				if(yes == 1)	break;
    			}
    			if(yes == 1)	word[j][i] = word[j+1][i]+1; 
    			else			word[j][i] = word[j+1][i];
   			}
//*************************************************************************
/*    i : c0[i-1]    j :c0[j-1]  st       dp[i][j][st] */
  		for(st = 1; st <= k; st++)
   			for(i = 0; i < len-st+1; i++)
    			for(j = i+st-1; j < len; j++)
				{
     				if(st == 1)
					{
						dp[i][j][st] = word[i][j]; 
						continue; 
					}
     			for(max = 0, l = i+st-2; l < j; l++) 
				{
      				x = dp[i][l][st-1]+word[l+1][j];
      				if(x > max)	max = x;
     			}
     			dp[i][j][st] = max;
    			}
//************************************************************************
  		printf("%d
", dp[0][len-1][k]);
 	}
 	return 0;
}