Почему правильное ДП всё равно даёт TLE и как его ускорить, не меняя логику?
Написал ДП с корректной асимптотикой (по прикидке должно проходить), но всё равно TLE. Алгоритм менять вроде не на что — асимптотика уже теоретически нормальная. Какие есть способы ускорить ДП константно, без смены подхода?
2 ответа
Если асимптотика верная, но TLE — это проблема константы. Чеклист:
- Память и кэш. Замени
vector<vector<int>>на одномерныйvector<int>с ручной индексациейdp[i*M+j]или статический массив. Многомерные vector'ы плохо ложатся в кэш. Перебирай индексы так, чтобы внутренний цикл шёл по последнему (непрерывному) измерению. - Сжатие до O(W) по памяти (как в рюкзаке) — меньше промахов кэша.
- Тип данных.
intбыстрееlong long; не бериlong longбез нужды. Но и не словись на переполнении — взвешивай. - Ввод/вывод.
scanf/printfилиios::sync_with_stdio(false); cin.tie(0);— медленный ввод сам по себе даёт TLE при больших данных. - Лишние пересчёты. Выноси из внутреннего цикла всё, что не зависит от его переменной (cost, индексы).
ios::sync_with_stdio(false); cin.tie(nullptr);
static int dp[2][MAXM]; // катящиеся два слоя вместо n×M
Если всё это не спасает — асимптотика на самом деле не проходит, и нужна одна из оптимизаций перехода (монотонная очередь, CHT, Кнут, D&C). Прикинь точно число операций: ~10^8 простых операций ≈ 1 сек.
Частая скрытая причина TLE при «правильной» асимптотике — тяжёлый переход. Например, в каждом состоянии ты внутри делаешь lower_bound, map, копирование вектора или вызов функции по значению. O(n²) с map внутри это фактически O(n² log n) с огромной константой. Замени map на массив/unordered_map с резервом, передавай по ссылке (const&), убери endl (он флашит буфер — бери '\n'). Профилируй мысленно стоимость одной итерации внутреннего цикла: часто там прячется лишний логарифм или аллокация.