Дисклеймер: способ, описанный ниже, не является универсальным, однако зачастую может решить задачу или помочь прийти к правильному решению.
Если задача сводится к тому, что необходимо разбить массив на непересекающиеся подотрезки (последовательность подряд идущих элементов) оптимальным образом (или посчитать количество подходящих разбиений), то стоит попробовать решить ее с помощью динамического программирования.
Примерная схема решения такая:
dp[i] - ответ для первых i элементов
Подсчет dp[i]: так как мы рассматриваем только первые i элементов, то i-й будет последним и значит, что этот элемент будет в последнем подотрезке и при этом самым правым там. Поэтому мы можем перебрать левую границу последнего подотрезка j. В процессе перебора будем подсчитывать значение этого подотрезка и если он является корректным, то пересчитаем dp[i] через dp[j - 1] и значение подотрезка [j;i].
Рассмотрим следующую простую задачу: дан массив из целых чисел, необходимо разбить его на минимальное количество непересекающихся подотрезков, чтобы каждое число входило в какой-нибудь подотрезок и чтобы в каждом подотрезке были одинаковые числа. Например, для массива 1 2 2 3 3 3 2 1 1 оптимальное разбиение выглядит так: [1] [2 2] [3 3 3] [2] [1 1]. Эта задача несложно решается простым проходом по массиву (все одинаковые подряд идущие элементы помещаем в один подотрезок), но мы решим ее с помощью динамического программирования для примера.
int n;
cin >> n;
// заполняем массив с 1-индексацией
vector arr(n + 1);
for (int i = 1; i <= n; i++)
cin >> arr[i];
// изначально ставим +оо в значения дп
vector dp(n + 1, 1000000000);
// массив длины ноль разбивать не нужно, поэтому для него ответ 0
dp[0] = 0;
// считаем ответ для dp[i] по возрастанию i
for (int i = 1; i <= n; i++) {
// в текущий момент arr[i] - последний элемент, значит он будет самым правым числом в последнем подотрезке
// переберем все варианты того, где этот последний подотрезок начинался
for (int j = i; j > 0; j--) {
if (arr[j] != arr[i]) {
// если встретили элемент, который не равен последнему, то подотрезок будет содержать разные числа, а это не подходит по условию
// продолжать уже нет смысла, т.к. сдвигая левую границу левее, этот элемент не пропадет, поэтому делаем break
break;
}
// представляем, что последний подотрезок был [j;i]
// значит надо взять оптимальное разбиение первых j-1 элементов и прибавить 1 (сам подотрезок [j;i])
dp[i] = min(dp[i], dp[j - 1] + 1);
}
}
cout << dp[n];
Если элементы могут не принадлежать ни одному из подотрезков, то необходимо просто рассмотреть соответствующий вариант, как dp[i] = dp[i - 1]