Почему мое жадное решение дает неправильные ответы на задачу «Отпуск»? Путаница в логике DP при минимизации дней отдыха ⇐ C++

[Anonymous]

Почему я не могу использовать жадность?

Постановка задачи:
https://codeforces.com/problemset/problem/698/A
Что я сделал, так это предположим, что кусок из троек имеет четную длину, тогда, если соседи разные, мы можем создать шаблон без остатка (1332 можно изменить на 1212), но если длина нечетная, мы соседи должны быть одинаковыми (13331 можно изменить на 12121). В остальных случаях вася отдохнет
но на больших случаях не получается
#include
#define ll long long
#define pb push_back
#define nl '\n'
#define vi vector
#define vvi vector
#define f(i, n) for (ll i = 0; i < n; i++)
using namespace std;
void solve()
{
int n;
cin >> n;
vector ar(n);
f(i, n)
cin >>
ar;

int prev = -1, c2 = 0, c1 = 0;
for (int i = 0; i < n; i++)
{
if (ar == 3)
{
int l = i, r = i;
while (r < n and ar[r] == 3)
r++;
if (r < n and i != 0)
{
int len = r - l;
if (len % 2 == 0 and ar[l - 1] != ar[r])
c1 += len;
else if (len % 2 and ar[l - 1] == ar[r])
{
// cout

Подробнее здесь: https://stackoverflow.com/questions/798 ... oblem-dp-l