Ciao, sto provando a risolvere prankster, con l’idea che il costo minimo si possa ottenere suddividendo la sequenza in input in sottosequenze palindrome, saltando gli eventuali 0 iniziali, 0 finali e 0 tra le sottosequenze palindrome, e sommando i costi minimi per ciascuna di esse, con l’ipotesi che il costo minimo per una sequenza palindroma sia la metà della sua lunghezza aumentata di uno.
Questa idea funziona per i primi tre subtask, ma alcuni casi del quarto e quinto falliscono; non sono riuscito a trovare controesempi: potete aiutarmi?
Comunque va in TLE sul sesto subtask, quindi immagino che dovrò pensare a qualcos’altro.
Ecco il mio codice:
#include <bits/stdc++.h>
using namespace std;
bool palindromep (vector<int>::iterator beg, vector<int>::iterator end)
{
bool ret = true;
while (beg < end)
{
if (*(beg++) == *(end-- -1)) continue;
ret = false;
}
return ret;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifdef EVAL
assert(freopen("input.txt", "r", stdin) != NULL);
assert(freopen("output.txt", "w", stdout) != NULL);
#endif
int N; cin >> N;
vector<int> S(1); cin >> S[0];
for (int i = 1; i < N; i++)
{
int s; cin >> s;
// squeeze repeated digits
if (s == S.back()) continue;
S.push_back(s);
}
auto beg = S.begin(), end = S.end();
if (*prev(end) == 0) --end; // skip last digit if good
int c = 0; // cost
for (auto it = end; beg != end; beg = it, it = end)
{
if (*beg == 0) ++beg; // skip first digit if good
// select the longest palindromic subarray starting at beg
while (!palindromep (beg, it)) --it;
c += (int) (it-beg+1) / 2; // palindromic cost
}
cout << c << endl;
return 0;
}