Puoi leggere e provare a risolvere questo problema visitando questo indirizzo ristorante
Innanzitutto possiamo notare che se ci sono due piatti dello stesso tipo con lo stesso prezzo, possiamo prendere solo il piatto che appare per primo tra i due, perciò possiamo troncare l'array appena troviamo un prezzo già incontrato. Possiamo fare ciò iterando sugli array e utilizzando una std::map
oppure una std::unordered_map
.
Dati due array e , definiamo prefix_X_Y
un array di elementi tale che prefix_X_Y[i]
è uguale alla massima lunghezza del prefisso di che non contiene nessuno dei primi elementi di . Notiamo che se aggiungiamo un elemento di , il prefisso di può accorciarsi oppure rimanere uguale, perciò prefix_X_Y
è ordinato in ordine decrescente. Per calcolare prefix_X_Y
possiamo usare una mappa contenente le posizioni dei valori di all'interno dell'array, poi ci basta iterare sugli elementi di e ad ogni iterazione controllare se il prefisso di rimane uguale oppure si restringe.
Calcoliamo prefix_A_S
, prefix_P_S
e prefix_A_P
. Fissati due prefissi di e di lunghezza rispettivamente e :
Per ottenere la soluzione ci basta quindi iterare su tutti i possibili valori e e restituire il valore più grande tra quelli ottenuti, la complessità è .
#include "bits/stdc++.h"
using namespace std;
int distinct_prefix(vector<int>& V) {
unordered_set<int> taken;
for (int x : V) {
if (!taken.insert(x).second) {
break;
}
}
V.resize(taken.size());
return taken.size();
}
vector<int> longest_prefix(vector<int>& A, vector<int>& B) {
unordered_map<int, int> pos;
for (int i = 0; i < B.size(); i++) {
pos[B[i]] = i;
}
vector<int> pref(A.size() + 1);
pref[0] = B.size();
for (int i = 0; i < A.size(); i++) {
pref[i + 1] = pref[i];
if (auto it = pos.find(A[i]); it != pos.end()) {
pref[i + 1] = min(pref[i + 1], it->second);
}
}
return pref;
}
int conta(int N, vector<int>& A, vector<int>& P, vector<int>& S) {
int Na = distinct_prefix(A);
int Np = distinct_prefix(P);
int Ns = distinct_prefix(S);
vector<int> prefix_A_P = longest_prefix(A, P);
vector<int> prefix_A_S = longest_prefix(A, S);
vector<int> prefix_P_S = longest_prefix(P, S);
int res = 0;
for (int ka = 0; ka <= Na; ka++) {
for (int kp = 0; kp <= prefix_A_P[ka]; kp++) {
res = max(res, ka + kp + min(prefix_A_S[ka], prefix_P_S[kp]));
}
}
return res;
}
Fissato un determinato , notiamo che prefix_P_S
è ordinato in ordine decrescente, per cui possiamo trovare un valore tale che:
Per trovare possiamo fare una ricerca binaria su prefix_P_S
. Per calcolare la soluzione per un certo abbiamo due casi:
Notiamo che il valore dell'espressione dipende da :
nel caso 1 e sono fissati per cui per massimizzare l'espressione è sufficiente massimizzare . Sappiamo che , quindi possiamo scegliere :
nel caso 2 dobbiamo invece massimizzare :
Per trovare la soluzione finale possiamo quindi iterare su tutti i possibili valori e calcolare per ciascuno di essi i casi 1 e 2, la complessità è .
#include "bits/stdc++.h"
using namespace std;
constexpr int MAXN = 1 << 17;
int seg[2 * MAXN];
void st_build(vector<int>& V) {
for (int i = 0; i < V.size(); i++) {
seg[i + MAXN] = i + V[i];
}
for (int i = MAXN - 1; i > 0; i--) {
seg[i] = max(seg[2 * i], seg[2 * i + 1]);
}
}
int st_query(int l, int r) {
int res = 0;
for (l += MAXN, r += MAXN; l < r; l /= 2, r /= 2) {
if (l % 2) res = max(res, seg[l++]);
if (r % 2) res = max(res, seg[--r]);
}
return res;
}
int distinct_prefix(vector<int>& V) {
unordered_set<int> taken;
for (int x : V) {
if (!taken.insert(x).second) {
break;
}
}
V.resize(taken.size());
return taken.size();
}
vector<int> longest_prefix(vector<int>& A, vector<int>& B) {
unordered_map<int, int> pos;
for (int i = 0; i < B.size(); i++) {
pos[B[i]] = i;
}
vector<int> pref(A.size() + 1);
pref[0] = B.size();
for (int i = 0; i < A.size(); i++) {
pref[i + 1] = pref[i];
if (auto it = pos.find(A[i]); it != pos.end()) {
pref[i + 1] = min(pref[i + 1], it->second);
}
}
return pref;
}
int conta(int N, vector<int>& A, vector<int>& P, vector<int>& S) {
int Na = distinct_prefix(A);
int Np = distinct_prefix(P);
int Ns = distinct_prefix(S);
vector<int> prefix_A_P = longest_prefix(A, P);
vector<int> prefix_A_S = longest_prefix(A, S);
vector<int> prefix_P_S = longest_prefix(P, S);
st_build(prefix_P_S);
int res = 0;
for (int ka = 0; ka <= Na; ka++) {
int L = distance(lower_bound(prefix_P_S.rbegin(), prefix_P_S.rend(), prefix_A_S[ka]),
prefix_P_S.rend());
res = max(res, ka + min(L - 1, prefix_A_P[ka]) + prefix_A_S[ka]); // caso 1
res = max(res, ka + st_query(L, prefix_A_P[ka] + 1)); // caso 2
}
return res;
}
Notiamo che all'aumentare di , il valore di aumenta oppure rimane uguale, possiamo quindi sostituire la ricerca binaria con un puntatore a prefix_P_S
, ad ogni iterazione di possiamo incrementare il puntatore fino al suo nuovo valore.
Notiamo che invece è decrescente all'aumentare di . Quindi ad ogni iterazione di , l'intervallo potrebbe ridursi ma non può espandersi da nessuna delle due estremità.
Possiamo quindi iterare sui valori di al contrario, facendo ciò l'intervallo può, al contrario, soltanto espandersi. Perciò anziché utilizzare un segment tree possiamo semplicemente memorizzare in una variabile il valore massimo e aggiornarlo ad ogni iterazione con i nuovi elementi dell'intervallo.
La complessità ad ogni iterazione di è ammortizzato, quindi la complessità finale è .
#include "bits/stdc++.h"
using namespace std;
int distinct_prefix(vector<int>& V) {
unordered_set<int> taken;
for (int x : V) {
if (!taken.insert(x).second) {
break;
}
}
V.resize(taken.size());
return taken.size();
}
vector<int> longest_prefix(vector<int>& A, vector<int>& B) {
unordered_map<int, int> pos;
for (int i = 0; i < B.size(); i++) {
pos[B[i]] = i;
}
vector<int> pref(A.size() + 1);
pref[0] = B.size();
for (int i = 0; i < A.size(); i++) {
pref[i + 1] = pref[i];
if (auto it = pos.find(A[i]); it != pos.end()) {
pref[i + 1] = min(pref[i + 1], it->second);
}
}
return pref;
}
int conta(int N, vector<int>& A, vector<int>& P, vector<int>& S) {
int Na = distinct_prefix(A);
int Np = distinct_prefix(P);
int Ns = distinct_prefix(S);
vector<int> prefix_A_P = longest_prefix(A, P);
vector<int> prefix_A_S = longest_prefix(A, S);
vector<int> prefix_P_S = longest_prefix(P, S);
int res = 0;
int L = Np + 1, R = 0;
int max_P_S = 0;
for (int ka = Na; ka >= 0; ka--) {
while (L > 0 && prefix_A_S[ka] > prefix_P_S[L - 1]) {
L--;
if (L < R) {
max_P_S = max(max_P_S, L + prefix_P_S[L]);
}
}
while (R <= prefix_A_P[ka]) {
if (L <= R) {
max_P_S = max(max_P_S, R + prefix_P_S[R]);
}
R++;
}
res = max(res, ka + min(L - 1, prefix_A_P[ka]) + prefix_A_S[ka]); // caso 1
res = max(res, ka + max_P_S); // caso 2
}
return res;
}