Почему здесь нельзя решать через жадный алгоритм?

Question

[dalbio]

Есть задача: https://codeforces.com/contest/1400/problem/E
Мой код:

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
int main() {
	IOS;
	int n;
	cin >> n;
	vector<int>a;
	a.resize(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	int len = 0;
//	int not1 = 0;
	//int y1 = 0;
	long long ans = 0;
	bool f = false;
	a.push_back(0);
	for (int i = 0; i <= n; i++) {
		if (a[i] == 0) {
			if (len > 1) {
				ans += 1;
				for (int j = i - len; j < i; j++) {
					a[j]--;
				}
			}
			//ans += len;
			len = 0;
			f = false;
		}
		else {
			if (f && a[i]>1) { 
				ans += 2; len = 0; 
				a[i] = 0;
				a[i - 1] = 0;
			}
			else len++;
			if (a[i] > 1) f = true;
			else f = false;
	//		if (a[i] == 1) y1++;
	//		else not1++;
		}
	}
	for (int i = 0; i < n; i++) {
		if (a[i] > 0) ans++;
	}
	cout << ans << "\n";
}

Идея в том что, сначала пройтись по непрерывным не нулевым под массивам, вычесть из каждого элемента 1,затем пройтись опять по массиву и добавить к ответу количество элементов >0,

if (f && a[i]>1) { 
				ans += 2; len = 0; 
				a[i] = 0;
				a[i - 1] = 0;
			}

Нужно,чтобы под массив например 2,2 удалялся за 2 хода,а не за 4.
Но всё равно решение неверное,почему?

Answer 1

[Wataru]

Почему не работает жадность? Вы же сами привели тест, на котором такая жадность не работает.

Могу еше привести пример. В {1, 2, 3, 2, 1} - ответ 3. Тут надо удалить отрезок 1..5, потом 2..4, потом 1 вхождение элемента 3, Если же форма будет немного другая, например {1, 100, 1000, 100, 1} - то ответ 4. После первого удаления отрезка надо удалять числа по одному.

В общем случае, жадное решение не работает, пока не доказанно обратное.
Одно ваше наблюдение, действительно, истинно - в оптимальном решении сначала делаются какие-то удаления отрезков, а потом удаляются целиком оставшиеся элементы по одному.

Это можно доказать так:

Рассмотрим какое-то решение (последовательность действий). Перенесем все удаления одиночных элементов в самый конец, возможно изменив количество удаляемых за раз элементов. Кроме того, объеденим несколько операций удаления одного и того же элемента в одну, просуммировав количества удаленных элементов. Все шаги-отрезки все так же можно выполнить, потому что мы только перетащили какие-то операции за них, поэтому перед шагом количество элементов могло только увеличится, а значит весь отрезок все так же не содержит нулей. Это решение имеет такое же количество шагов или меньше. Значит можно искать оптимальное решение именно такого вида.

Многие жадности доказывается похожими рассуждениями, без применения теории матроидов: Рассмотрите ответ, как-то его поменяйте, чтобы он обладал свойствами, которые получаются вашей жадностью. если он при этом становится не хуже - вы доказали что так делать можно.

Пока вы так не докажите свой алгоритм, можно смелло считать, что есть еще какой-то тест, где он выдаст не оптимальный ответ.

Подсказка1: посмотрите на ограничения. n всего лишь 5000. Значит, подразумеватся решение за квадрат. Посмотрите на теги.

Подсказка2: Можно смотреть на эту задачу так - есть башенки из кубиков высоты a[i]. Можно за раз или покрасить вертикальный отрезок башни у самого верха, или покрасить какой-то горизонтальный отрезок кубиков. Надо покрасить все кубики за наименьшее количетсво шагов. Тут только неочевидно, почему нужно красить горизонтальные отрезки, ведь несколько операций удаления отрезка могут пересекатся. Но тут поможет рассуждение как выше, через изменение любого ответа. Эти операции можно сложить как доски, в виде пирамид, т.ч. верхние операции целиком лежат в нижних операциях. От этого ответ станет не хуже.

Еще подсказка, подумайте, как можно убрать самый высоко стоящий кубик, какие варианты?