고지 사항: 아래에 설명된 방법은 보편적이지 않지만 종종 문제를 해결하거나 올바른 솔루션을 찾는 데 도움이 될 수 있습니다.
문제가 배열을 교차하지 않는 하위 세그먼트(연속 요소 시퀀스)로 최적의 방식으로 분할(또는 적합한 분할 수 계산)해야 한다는 사실로 귀결되는 경우 해결을 시도할 가치가 있습니다. 동적 프로그래밍을 사용합니다.
솔루션 체계의 예는 다음과 같습니다.
dp[i] - 첫 번째 i 요소에 대한 응답
dp[i] 계산: 첫 번째 i번째 요소만 고려하고 있으므로 i번째 요소가 마지막 요소가 됩니다. 즉, 이 요소는 마지막 하위 세그먼트에 있고 동시에 가장 오른쪽에 있습니다. 따라서 마지막 하위 세그먼트 j의 왼쪽 경계를 반복할 수 있습니다. 열거하는 과정에서 이 subsegment의 값을 계산하고 맞다면 dp[i]부터 dp[j - 1]까지 그리고 subsegment [j;i]의 값을 다시 계산합니다.
다음과 같은 간단한 문제를 생각해 보십시오. 정수 배열이 주어졌을 때 각 숫자가 일부 하위 세그먼트에 포함되고 각 하위 세그먼트에 동일한 숫자가 포함되도록 최소 개수의 교차하지 않는 하위 세그먼트로 분할해야 합니다. 예를 들어 배열 1 2 2 3 3 3 2 1 1의 경우 최적 분할은 다음과 같습니다. [1] [2 2] [3 3 3] [2] [1 1]. 이 작업은 배열을 통과하는 것만으로 쉽게 해결되지만(동일한 연속 요소를 모두 하나의 하위 세그먼트에 넣음) 예를 들어 동적 프로그래밍을 사용하여 해결합니다.
정수;
cin>> N;
// 배열을 1-인덱스로 채움
벡터 arr(n + 1);
for (int i = 1; i <= n; i++)
cin>> 도착[i];
// 초기에 +oo를 dp 값으로 설정
벡터 dp(n + 1, 1000000000);
// 길이가 0인 배열은 분할할 필요가 없으므로 이에 대한 대답은 0입니다.
dp[0] = 0;
// 오름차순 i에서 dp[i]에 대한 답을 계산합니다.
for (int i = 1; i <= n; i++) {
// 현재 arr[i]는 마지막 요소이므로 마지막 하위 세그먼트에서 가장 오른쪽 숫자가 됩니다.
// 이 마지막 하위 세그먼트가 시작된 위치에 대한 모든 옵션을 반복합니다.
for (int j = i; j > 0; j--) {
if (arr[j] != arr[i]) {
// 마지막 요소와 같지 않은 요소를 만나면 하위 세그먼트에 다른 숫자가 포함되며 이는 조건에 맞지 않습니다.
// 계속할 필요가 없습니다. 왜냐하면 왼쪽 테두리를 왼쪽으로 이동해도 이 요소는 사라지지 않으므로 중단합니다.
부서지다;
}
// 마지막 하위 세그먼트가 [j;i]라고 가정합니다.
// 따라서 첫 번째 j-1 요소의 최적 분할을 취하고 1을 더해야 합니다(하위 세그먼트 [j; i] 자체)
dp[i] = min(dp[i], dp[j - 1] + 1);
}
}
cout << dp[n];
요소가 하위 세그먼트에 속하지 않을 수 있는 경우 dp[i] = dp[i - 1]과 같이 적절한 옵션을 고려해야 합니다.