동적 계획 구간 DP 입문 (기초 초과)
(1) 합병: 곧 두 개 또는 여러 부분 을 통합 시 킬 것 이 고 당연히 반대로 할 수 있다.(2) 특징: 문 제 를 두 가지 합병 할 수 있 는 형식 으로 나 눌 수 있다.(3) 구 해: 전체 문 제 를 가장 좋 은 값 으로 버 리 고 합병 점 을 매 거 하 며 문 제 를 좌우 두 부분 으로 분해 하고 마지막 으로 합 친 두 부분의 가장 좋 은 값 은 원래 문제 의 가장 좋 은 값 으로 할 수 있다.
* 예제:
NC 13230 (답장 하위 문자열 통합)
제목 설명: 두 문자열 A 와 B 를 입력 하고 하나의 문자열 C 로 합 쳐 A 와 B 에 속 하 는 문 자 는 C 에서 순서 가 변 하지 않 습 니 다.예 를 들 어 'abc' 와 'xyz' 는 'axbycz' 나 'abxcyz' 등 으로 조합 할 수 있다.우 리 는 문자열 의 가 치 를 가장 긴 답장 문자열 의 길이 로 정의 합 니 다. (답장 문자열 은 정반 양쪽 에서 완전히 일치 하 는 문자열 을 표시 합 니 다. 예 를 들 어 "aba" 와 "xyyx")가능 한 모든 C 에서 가장 큰 값 을 가 진 문자열 을 구 해 야 합 니 다. 이 최대 값 을 출력 하면 됩 니 다.
입력 설명: 첫 줄 의 정수 T (T ≤ 50).다음 2T 줄 은 두 줄 마다 A, B (| A |, | B | ≤ 50), A, B 의 문자 집합 은 전체 소문 자 를 나타 낸다.
출력 설명: 각 그룹의 데이터 출력 에 대해 한 줄 의 정수 가 가장 큰 C 의 가 치 를 표시 합 니 다.
샘플:
：
2
aa
bb
a
aaaabcaa
：
4
5
++++++++++
DP 상태 분석: 저자: 왕 칭 링크 - >: 사고방식 상세 분석
Dp [i] [j] 까지 두 가지 상황 이 있 습 니 다.
그리고 두 꼬치 의 합병 은 바로 이 두 가지 상태 전이 방정식 의 서브 상태 로 코드 를 구체 적 으로 본다.
++++++++++
AC 코드 (times = 973 ms / 2000 ms):
// DP
#define _CRT_SECURE_NO_WARNINGS
#include
", ans);//
}
return 0;
}
NC 16129 (작은 도장공)
제목 설명: "lalala, 나 는 즐 거 운 도장공 입 니 다.""사장 님 은 목이 쉬 도록 소 리 를 질 렀 습 니 다. 고민 하 는 작은 이름 은 잘 리 고 싶 지 않 기 때문에 가능 한 한 빨리 벽 을 닦 고 싶 습 니 다. 본인 의 수학 기초 가 매우 좋 지 않 기 때문에 그 는 지금 당신 에 게 적어도 모든 벽 을 완성 하려 면 몇 번 을 닦 아야 하 는 지 계산 해 달라 고 부 탁 했 습 니 다. 각 벽 은 n 개의 단락 이 있 고 각 단락 에 목표 색 ci 를 지정 하 였 습 니 다. 처음에 모든 벽 은 흰색 이 었 습 니 다. 우 리 는 지금 하 나 를 가지 고 있 습 니 다.브러시 의 길 이 는 k 입 니 다. 브러시 는 매번 한 가지 색 을 선택 한 다음 (1 ~ k) 연속 적 인 벽 구간 을 선택 하여 선택 한 색 으로 칠 할 수 있 습 니 다. 벽 을 목표 색 으로 바 꾸 기 위해 서 는 최소한 몇 번 을 칠 해 야 하 는 지 알 고 싶 습 니 다.
* TIPS: 아 는 것 은 같은 문제 형 문 제 를 공 고 히 해 볼 수 있 습 니 다. 모 르 는 것 은 먼저 간단 한 버 전 NC 19909 를 만 들 수 있 습 니 다. 같은 유형 에 비해 이 문 제 는 간단 합 니 다.
입력 설명: 모든 사례 에 대해 우리 의 첫 번 째 줄 은 두 개의 정수 n, k (1 < = n < = 100, 1 < = k < = 50, k 를 포함 합 니 다.
출력 설명: 작은 이름 을 최소 몇 번 칠 하 는 지 를 나타 내 는 숫자 를 출력 합 니 다.
샘플:
：
3 3
1 2 1
：
2
++++++++++
：
5 4
5 4 3 3 4
：
3
++++++++++
DP 상태 분석: 저자: 돌아 오 는 꿈 의 링크: 사고의 출처 dp [i] [j] 는 i 번 째 위치 에서 j 번 째 위치 까지 필요 한 최소 걸음 수 (n 은 솔 의 길이, k 는 매 거 진 구간 단점) 의 첫 번 째 상황 을 나타 낸다. n > = len 일 때 (len 은 현재 매 거 진 길이) 우 리 는 직접 그 릴 수 있다. 우 리 는 매 거 진 단점 k 일 때 a [i] = a [k] 를 먼저 판단 할 수 있다.만약 에 똑 같이 dp [i] [j] = min (dp [i] [j], dp [i + 1] [k] + dp [k + 1] [j]) 이 있 으 면 최소 조작 횟수 는 i 번 째 와 k 번 째 를 함께 바 르 는 것 이기 때문에 구간 [i, j] 에서 점 i 를 하면 두 번 째 상황 을 고려 하지 않 아 도 된다.
구체 적 분석 코드 참조
++++++++++
AC 코드 (times = 4ms / 1000 ms):
// DP
#define _CRT_SECURE_NO_WARNINGS
#include
", dp[1][n]);//
return 0;
}
NC 19973 ([HAOI] 완구 작명)
제목 설명: 누 군 가 는 장난감 한 벌 을 가지 고 장난감 의 이름 을 붙 이려 고 한다. 먼저 그 는 WING 네 글자 중 하 나 를 장난감 의 기본 이름 으로 선택한다. 그리고 그 는 자신의 취향 에 따라 이름 중 하 나 를 'WING' 로 사용한다.중 임의의 두 글자 로 대체 하여 자신의 이름 을 매우 길 게 늘 릴 수 있 게 한다. 지금 그 는 어떤 긴 이름 이 처음에는 어떤 자모 로 변 형 됐 는 지 맞 춰 보고 싶 어 한다.
입력 설명: 첫 줄 의 네 개의 정수 W, I, N, G 입 니 다. 각 자 모 는 몇 개의 두 글자 로 대체 할 수 있 음 을 의미 합 니 다. 다음 줄 의 W 줄 은 두 글자 로 W 를 대체 할 수 있 음 을 의미 합 니 다. 다음 줄 의 I 줄 은 두 글자 로 대체 할 수 있 음 을 의미 합 니 다. 다음 줄 의 N 줄 은 두 글자 로 N 을 대체 할 수 있 음 을 의미 합 니 다. 다음 G 줄 은 두 글자 로 대체 할 수 있 음 을 의미 합 니 다.줄, 줄 마다 두 글자, G 는 이 두 글자 로 대체 할 수 있 음 을 표시 합 니 다. 마지막 줄 의 길 이 는 Len 을 초과 하지 않 는 문자열 입 니 다. 이 장난감 의 이름 을 표시 합 니 다.
출력 설명: 한 줄 의 문자열 입 니 다. 이 이름 은 어떤 자모 로 변 형 될 수 있 습 니까? (WING 순서대로 출력) 주어진 이름 이 어떤 자모 로 변 형 될 수 없 으 면 "The name is wrong!" 을 출력 합 니 다.
샘플:
：
1 1 1 1
II
WW
WW
IG
IIII
：
IN
++++++++++
DP 상태 분석: 저자: 회귀 의 꿈 링크: 사고의 출처 dp [i] [j] [k] 는 구간 [i, j] 이 k 에서 전 환 된 것 인지, is [i] [j] [k] 는 i 가 구간 [l, r] 을 j, k 두 글자 로 대체 할 수 있 는 지, 중간 점 은 k, z, z1, z2 는 1 ~ 4 로 WING (z, z1, z2 는 코드 에 따라 더 잘 이해 할 수 있 음) 를 나타 낸다. 만약 왼쪽 구간 [l, k + 1] 이 z1 에서 전 환 될 수 있다 면(즉, 코드 dp [l] [k] [z1]), 오른쪽 구간 [k + 1, r] 은 z2 로 전환 할 수 있 습 니 다 (코드 dp [k + 1] [r] [z2]), z 는 z1 과 z2 로 대체 할 수 있 습 니 다 (코드 (원작 자 오류, 변경) is [z] [z1] [z2]). 그것 은 구간 [l, r] 이 z 로 전환 되 었 음 을 설명 하 는 것 입 니까? (z1, z2 는 중간 역 으로 구간 [l, r] 과 z 를 연결 하 는 데 사 용 됩 니 다) tips: 코드 를 결합 하여 이해 합 니 다.
구체 적 인 내용 은 코드 참조
++++++++++
AC 코드 (time = 74ms / 1000 ms)
// DP
#define _CRT_SECURE_NO_WARNINGS
#include NC 20238 ([SCOI 2003] 문자열 접 기)
제목 설명: 접 는 정 의 는 다음 과 같 습 니 다. 하나의 문자열 은 그 자체 의 접 는 것 으로 볼 수 있 습 니 다. S = S X (S) 는 X (X > 1) 개의 S 가 연 결 된 문자열 의 접 는 것 입 니 다. X (S) = SSSS... S (X 개 S) 로 기록 합 니 다. A = A ', B = B' 라면 AB = A 'B' 예 를 들 어 3 (A) = AAA, 2 (B) = BB 이기 때문에 3 (A) C2 (B) = AAACBB, 2 (A) C) 2 (B)= AAAAAAACBB 는 가장 짧 은 접 기 를 원 하 는 문자열 을 줍 니 다. 예 를 들 어 AAAAAAAAAABABABCCD 의 가장 짧 은 접 기 는 9 (A) 3 (AB) CCD 입 니 다.
입력 설명: 한 줄, 즉 문자열 S 입 니 다. 길 이 는 100 을 초과 하지 않 습 니 다.
출력 설명: 한 줄, 즉 가장 짧 은 접 기 길이 입 니 다.
샘플:
：
NEERCYESYESYESNEERCYESYESYES
：
14
++++++++++
DP 상태 분석: dp [l] [r] 는 l ~ r 의 최 단 접 는 길이 dp [l] [r] = min (r - l + 1, dp [l] [k] + dp [k + 1] [r]) (l < = k 당 구간 [k + 1, r] 이 구간 [l, k] 에서 중복 할 수 있 을 때 dp [l] [r] = min (dp [l] [r], dp [l] [l] [l] [l] [l] [k] + 2 + getnum (r - l + 1) / (k - l + 1) -) 2 는 괄호 가 차지 하 는 자릿수 를 말 하 며 getnum 은 계수 가 차지 하 는 자릿수 를 말한다.
구체 적 분석 코드 참조
++++++++++
AC 코드 (times = 3ms / 1000 ms)
#define _CRT_SECURE_NO_WARNINGS
#include
", dp[1][len]);//
return 0;
}
요약: 문 첫머리 에 따라 문제 유형 을 판단 하여 구간 DP 로 확인 한 후 DP 방정식 을 무조건 에서 조건 부 제약 으로 전달 하여 상태 전이 방정식 을 도 출하 고 템 플 릿 을 채 우 면 된다.
* 첫 접촉 구간 DP, 오류 가 있 으 면 큰 사람 이 지적 해 주세요.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
JZOJ.3432 [GDOI 2014 시뮬레이션] 서버 문제 해결 보고서이 서버의 번호는 1, 2,..., n이다.우선, 우리는 일부 서버를 선택하여 파일을 그것들에 직접 복사할 수 있다.서버 i에 파일을 복사하려면 ci가 필요합니다.직접 복제를 통해 파일을 얻지 못한 서버에 대해 i+...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
