CodeForces 17C Balance (DP)

제목 유형  DP
제목
최대 150 자 길이 의 a 또는 b 또는 c 로 구 성 된 문자열 을 보 여 줍 니 다.
모든 작업 에 대해 서 는 앞의 문 자 를 뒤의 문자 로 바 꾸 거나 뒤의 문 자 를 앞의 문자 로 바 꿀 수 있 습 니 다. 
즉, 할당 문 구 를 실행 할 수 있 습 니 다 str [i + 1] = str [i];또는 str [i] = str [i + 1];
하면, 만약, 만약...
문자열 은 여러 번 의 작업 을 수행 한 후에 a, b, c 의 문자 수가 서로 1 을 초과 하지 않 는 문자열 로 변 합 니 다. 이 문자열 을 합 법 적 인 문자열 이 라 고 합 니 다.
합 법 꼬치 가 몇 개 냐 고.
예 를 들 어 입력 문자열 aaacb 중 a 는 3 개, b 는 1 개, c 는 1 개 3 - 1 > 1 이 합 법 적 이지 않 습 니 다. 
하지만 세 번 째 a 는 c - > aaccb a 는 2 개, b 는 1 개, c 는 2 개 로 서로 간 의 수량 이 1 을 초과 하지 않 기 때문에 aaccb 는 합 법 적 인 꼬치 입 니 다.
문제 풀이 방법
입력 한 문자열 이 A 라 고 가정 하면 문자열 A '는 A 문자열 의 같은 문 자 를 하나의 결과 로 압축 합 니 다 (예 를 들 어 aacbbb 는 acb 로 압축 합 니 다).
합 법 적 인 문자열 B 를 가정 하면 B '는 B 압축 된 문자열 입 니 다. 
이때 B 가 A 가 몇 번 의 조작 을 통 해 얻 은 결과 라면 B '는 A' 의 하위 서열 임 을 발견 할 수 있다.
만약 에 B '가 A' 의 하위 서열 이 라면 B 는 A 에서 몇 번 의 조작 을 통 해 얻 을 수 있다 는 것 을 의미한다.
이렇게 하면 자 연 스 럽 게 하나의 배열 dp [i] 로 A '의 i 번 째 문 자 를 마지막 으로 하 는 문자열 의 수 를 나 타 낼 수 있다.
제목 은 문자 a, b, c 의 수량 이 서로 1 을 초과 하지 않도록 요구 하기 때문에 문자 a, b, c 가 사용 한 수량 을 동시에 기록 해 야 합 니 다.
상태 dp [i] [na] [nb] [nc] 는 A '의 i 번 째 문 자 를 마지막 으로 하 는 문자 a 의 수량 은 na 이 고 문자 b 의 수량 은 nb 이 며 문자 c 의 수량 은 nc 의 문자열 의 수량 을 나타 낸다.
A '에 서 는 앞 에 있 는 문자 만 뒤에 있 는 문 자 를 업데이트 할 수 있 기 때문에 현재 상태 로 뒤의 상 태 를 계속 업데이트 합 니 다. 뒤의 상태 로 매 거 졌 을 때 이 상태 가 가장 좋 습 니 다.
업데이트 시 완전 가방 사상, 즉 현재 상태 뒤에 임의의 a 또는 b 또는 c 를 추가 할 수 있 습 니 다.
if (구조의 다음 문 자 는 a) dp [next [i]] [na + 1] [nb] [nc] + = dp [i] [na] [nb] [nc];next [i] 만족 조건 표시 (A '[j] = =' a '& & j > = i) 중 가장 작은 j 
if (구조의 다음 문 자 는 b) dp [next [i]] [na] [nb + 1] [nc] + = dp [i] [na] [nb] [nc];next [i] 만족 조건 표시 (A '[j] = =' b '& & j > = i) 중 가장 작은 j 
if (구조의 다음 문 자 는 c) dp [next [i]] [na] [nb] [nc + 1] + = dp [i] [na] [nb] [nc];next [i] 는 만족 조건 (A '[j] = =' c '& j > = i) 중 가장 작은 j 를 나타 낸다.
왜 제일 작은 j 야?만약 가장 작은 j 가 아니라면 일부 문 자 를 낭비 하 게 할 수 있 습 니까?
합 법 적 인 문자열 을 요구 하 는 a, b, c 문자 의 수량 이 서로 1 을 초과 하지 않 기 때문에 문자열 의 길이 n% 3 = = 0 이면 a, b, c 문자 의 수량 은 모두 n / 3 이다. 
                                   문자열 길이 n% 3 = = 1 이면 a, b, c 문자 수 는 n / 3 + 1, n / 3, n / 3 또는 n / 3, n / 3 + 1, n / 3 또는 n / 3, n / 3, n / 3, n / 3, n / 3 + 1 일 수 있 습 니 다.
                             문자열 길이 n% 3 = = 2 이면 a, b, c 문자 수 는 n / 3, n / 3 + 1, n / 3 + 1 또는 n / 3 + 1, n / 3, n / 3 + 1 또는 n / 3 + 1, n / 3 + 1, n / 3 + 1, n / 3
즉, na, nb, nc 의 최대 치 는 50 에 불과 하 다.
그래서 시간 복잡 도 는 약 150 * 50 * 50 = 18750000 시간 을 초과 하지 않 습 니 다.
참조 코드 - 궁금 한 점 이 있 으 시 면 아래 에 댓 글 을 남 겨 주시 면 바로 답 해 드 리 겠 습 니 다.

#include 
#include 
#include 
#include 
#include 
#include