다이내믹 프로그래밍 문제가

Question

사람이 나를 저녁 식사에가는 길에 this problem

을위한 최적의 동적 프로그래밍 알고리즘을 찾을 수는 CCC의 경쟁은 맛있는 곱슬 감자 튀김을 위해 일렬로 늘어서있다. N (1 ≤ N ≤ 100) 명의 경쟁자는 카페테리아에 들어가기 위해 단일 파일을 정렬했습니다.

CCC를 운영하는 Doctor V는 프로그래머가 다른 언어를 사용하는 프로그래머 옆에 선 서서 단순히 싫어한다는 것을 깨달았습니다. 고맙게도 CCC에서는 Gnold와 Helpfile의 두 가지 언어 만 허용됩니다. 또한, 경쟁자들은 적어도 K (1 ≤ K ≤ 6) 명의 경쟁자 그룹에 속할 경우에만 카페테리아에 입장 할 것이라고 결정했습니다.

* He will find a group of K or more competitors who use the same language standing next to each other in line and send them to dinner. 
* The remaining competitors will close the gap, potentially putting similar-language competitors together. 

그래서 의사 V가 당신을 위해 경쟁사의 순서를 기록했다

박사 V는 다음과 같은 방식을 반복하기로 결정했다. 모든 경쟁자가 식사를 할 수 있습니까? 그렇다면 저녁에 보내는 경쟁사 그룹의 최소 수는 얼마입니까? 첫 번째 라인은 두 정수를 포함

입력 N 및 K. 번째 행은 하나의 행에서의 경쟁 (H는 G가 Gnold를 나타내고, HELPFILE를 나타낸다) 출력

출력 시퀀스이다 N자를 포함 줄, 저녁 식사를 위해 형성되는 그룹의 최소 숫자 인 단일 숫자. 모든 프로그래머가 식사를 할 수없는 경우 -1을 출력합니다.

Answer 1

실용적인 방법으로 SPOJ 문제를 해결하고 싶지 않으므로 다음을 폴리 시간 DP의 존재 증거로 사용하십시오.

K가 고정되어 있으면 먹을 수있는 문자열 집합에 컨텍스트가 없습니다. G 및 H 대신 g 및 h을 사용하겠습니다. 한 다른 두 사이 그중 (및 - 하나 더 식사, 또는 적어도 K와 제 식당 DINES가 없다고 생각이

S -> ε | g S g S g S G | h S h S h S H 

G -> ε | g S G 

H -> ε | h S H 

같이 예를 들어, K = 3 번 문법 보인다 마지막과 끝에) 먹을 수있는 끈이있다.

지금 비어 있지 않은 S 제작 중량 1이 최소 가중치 파싱을 찾을 CYK 가중 변형을 사용하고, 다른 모든 K 고정 대한 무게 0. 가지고 CYK의 실행 시간은 O이다 (N ³).

Answer 2

하위 문제는 주어진 상태에 대해 모든 사람이 식사를하기 위해 필요한 최소한의 그룹입니다. 가능한 많은 행 상태가 있지만 실제로 보일 소수의 행 상태가 있으므로 메모 작성은 해시 맵을 사용하여 수행해야합니다.

여기에 몇 가지 의사 코드가 있습니다.

int dine(string line){ 
    if(hashmap.contains(line)){ 
     return hashmap.get(line); 
    } 
    if(line.length == 0){ 
     return 0; 
    } 
    best = N+1; 
    for(i=0;i<line.length;i=j){ 
     type = string[i]; 
     j = i+1; 
     while(type == string[j]){ 
      j++; 
     } 
     if(j-i >= K){ 
      result = dine(string.substring(0,i-1) + string.substring(j,string.length)); 
      if(result > 0 && result < best){ 
        best = result; 
      } 
     } 
    } 
    if(best == N+1){ 
     hashmap.insert(line, -1); 
     return -1; 
    } 
    else { 
     hashmap.insert(line, best+1); 
     return best+1; 
    } 
} 

이 줄에 대한 대답을 이미 찾은 경우 그 대답을 반환하십시오. 줄에 사람이 없다면 이미 끝났기 때문에 더 이상 그룹을 만들 필요가 없습니다.

그룹을 만들 수 없다고 가정합니다. 그런 다음 같은 생각을 가진 모든 프로그래머 그룹을 연속적으로 시도하여이 오류를 입증하십시오. 그룹이 선택하기에 충분히 큰 경우이 그룹을 삭제 한 후 재 방문을 허용하는 데 걸리는 이동 횟수를 확인하십시오. 필요한 최소한의 움직임을 추적하십시오.

모든 그룹을 제거 할 수있는 방법을 찾지 못하면 -1을 반환하십시오. 그렇지 않은 경우,이 단계에서 수행 한 이동을 설명하기 위해 하나의 그룹을 제거한 후 그룹을 제거한 후 필요한 최소 작업을 리턴하십시오.

Answer 3

나누기와 정복은 어떻습니까? 중간에 어딘가에 (탈착 가능한) 그룹을 가져 가면 두 그룹이 그것의 어느 쪽이든 말합니다 ... HHHGGGGHHHHH .... - 이제 두 가지 가능성이 있습니다. 같은 그룹에 두 세트의 H가 들어 있거나 그렇지 않습니다. 그들이 같은 그룹에서 식사를했다면 그들 사이의 G는 의 그룹으로 정확하게 제거되어야합니다. 그 G 's (그래서 당신은 첫 번째 이동으로 시도 할 수도 있습니다). 그렇지 않은 경우 왼쪽 및 오른쪽 하위 목록을 별도로 해결할 수 있습니다. 두 경우 모두 재발생 목록이 짧습니다.