Warum gibt meine gierige Lösung falsche Antworten auf das Problem „Urlaub“? DP-Logikverwirrung bei der Minimierung von R ⇐ C++

[Anonymous]

Warum kann ich hier nicht Greedy verwenden?

Was ich getan habe, war, dass wir sagen, der 3er-Block hat eine gerade Länge. Wenn die Nachbarn unterschiedlich sind, können wir ein Muster ohne Pause erstellen (1332 kann in 1212 geändert werden). Wenn die Länge jedoch ungerade ist, müssen die Nachbarn gleich sein (13331 kann in 12121 geändert werden). Für die übrigen Fälle wird Vasya eine Pause machen

aber bei größeren Fällen schlägt es fehl

Code: Select all

#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;
int ar[n] = {};
f(i, n)
cin >>
ar[i];

int prev = -1, c2 = 0, c1 = 0;
for (int i = 0; i < n; i++)
{
if (ar[i] == 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