POJ 3267 The Cow Lexicon(dp)
9703 단어 icon
상태 이동은 비교적 좋은 손잡이라고 할 수 있지만 일치하는 문자열은 시간을 초과하기 쉽다. 이전의 어떤 문제의 용법과 유사하다. i자모에서 j자모로 단어가 일치하면 dp[j]=dp[i-1]+j-i-l[k]+1을 찾아 작게 하면 된다.
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <cmath>
5 #include <algorithm>
6 using namespace std;
7 int dp[501];
8 char str[601][31],s1[601],l[601];
9 int num,n,len;
10 int main()
11 {
12 int i,j,k,u;
13 scanf("%d%d",&n,&len);
14 scanf("%s",s1);
15 for(i = 1; i <= n; i ++)
16 {
17 scanf("%s",str[i]);
18 l[i] = strlen(str[i]);
19 }
20 for(i = 0; i <= len-1; i ++)
21 {
22 dp[i] = i+1;
23 }
24 for(i = 0; i <= len-1; i ++)
25 {
26 for(j = 1; j <= n; j ++)
27 {
28 if(s1[i] == str[j][0])
29 {
30 num = 1;
31 if(l[j] == 1)
32 {
33 dp[i] = min(dp[i],dp[i-1]);
34 for(u = i+1;u <= len-1;u ++)
35 {
36 if(i-1 >= 0)
37 dp[u] = min(dp[u],dp[i-1]+u-i-l[j]+1);
38 else
39 dp[u] = min(dp[u],u-i-l[j]+1);
40 }
41 }
42 else
43 {
44 for(k = i+1; k <= len-1; k ++)
45 {
46 if(str[j][num] == s1[k])
47 {
48 num ++;
49 }
50 if(num == l[j])
51 {
52 for(u = k;u <= len-1;u ++)
53 {
54 if(i-1 >= 0)
55 dp[u] = min(dp[u],dp[i-1]+u-i-l[j]+1);
56 else
57 dp[u] = min(dp[u],u-i-l[j]+1);
58 }
59 break;
60 }
61 }
62 }
63 }
64 }
65 }
66 printf("%d
",dp[len-1]);
67 return 0;
68 }이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
draw.io에서 svg 아이콘을 추가하여 선과 채우기를 편집하고 싶습니다.에서 SVG로 다운로드 한 것을 사용. 아마 baseline-face-24px.svg 와 같은 파일명이 되어 있으므로, 텍스트 에디터로 열린다. (아래는보기 쉽도록 약간 성형되었습니다.) <path fill="non...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
