¡Hola!
Estuve viendo el problema Organizando las ventas de un mercachifle en el OIAJ. Intenté implementar distintas técnicas y al final terminé con la idea de que debería ser una DP, pero no logro llegar a una solución de 100 puntos. Ahí paso a explicar mi idea.
Mi idea
Siendo [a, b] el rango de un pedido, la idea es ordenar los pedidos de Alfio (lo voy a llamar A) y de Belén (la voy a llamar B). Luego, agregar unos pedidos señuelos que hagan de caso base que se ubicarían al final de cada lista de pedidos. De esta manera planteo una recursividad de esta manera:
para los pedidos de A y
para los pedidos de B. En donde e es la cantidad de pedidos que hay del respectivo dueño entre A[actual].a y B[i].a - 1 o B[actual].a y A[i].a - 1 según corresponda.
Para obtener e se deben tener otras listas con los pedidos pero ordenados por b. De esta manera, cuando se agarra un candidato del dueño opuesto, los pedidos del dueño actual que no interfieren con el candidato se encuentran adyacentes, solo basta con tener un contador que vaya aumentando si el a de este pedido es mayor o igual a A[actual].a (o B[actual].a según corresponda). Y si se tomase un candidato siguiente, bastaría seguir iterando por los propios pedidos y hacer la comprobaciones antes mencionadas (de esta manera se consigue revisar a todos los candidatos posibles y contar cuantos pedidos propios hay en medio en tiempo lineal).
Para recuperar el orden de selección de los pedidos basta indicar en cada pedido, el índice del pedido del dueño opuesto con el que maximizó su resultado.
Código
#include<bits/stdc++.h>
#define forn(i, n) for(int i = 0; i < n; i++)
#define fori(i, a, n) for(int i = a; i < n; i++)
#define fort(i, n) for(int i = 0; i <= n; i++)
#define forit(i, a, n) for(int i = a; i <= n; i++)
using namespace std;
const int MAXX = 1E8 + 5;
struct pedido{
int id, a, b;
pedido(int id, int a, int b) : id(id), a(a), b(b) {}
};
struct bya{
bool operator()(const pedido &a, const pedido &b){
return a.a < b.a;
}
};
struct byb{
bool operator()(const pedido &a, const pedido &b){
return a.b < b.b;
}
};
int A, B;
vector<int> dp[2], back[2];
vector<pedido> pAa, pBa, pAb, pBb;
int resolver(int it, bool w){
if(dp[w][it] != -1) return dp[w][it];
int aux, dentro = 0, ret = 0, bret = -1, e = 0;
if(w){ //Si es de B
fort(i, A){
if(pAa[i].a <= pBa[it].b) continue;
for(e; pBb[e].b < pAa[i].a; e++){
if(pBb[e].a < pBa[it].a) continue;
dentro++;
}
aux = dentro + resolver(i, 0);
if(aux > ret){
ret = aux;
bret = i;
}
}
} else{ //Si es de A
fort(i, B){
if(pBa[i].a <= pAa[it].b) continue;
for(e; pAb[e].b < pBa[i].a; e++){
if(pAb[e].a < pAa[it].a) continue;
dentro++;
}
aux = dentro + resolver(i, 1);
if(aux > ret){
ret = aux;
bret = i;
}
}
}
back[w][it] = bret;
return dp[w][it] = ret;
}
int main(){
ifstream cin("mercachifle.in");
ofstream cout("mercachifle.out");
int a, b, aux, res = 0, c = 0, d = 0;
pedido paux(4001, MAXX, MAXX); //Pedido señuelo
vector<int> rA, rB;
cin>>A;
forn(i, A){
cin>>a>>b;
pAa.push_back(pedido(i + 1, a, b));
pAb.push_back(pedido(i + 1, a, b));
}
cin>>B;
forn(i, B){
cin>>a>>b;
pBa.push_back(pedido(i + 1, a, b));
pBb.push_back(pedido(i + 1, a, b));
}
pAa.push_back(paux);
pBa.push_back(paux);
pAb.push_back(paux);
pBb.push_back(paux);
sort(pAa.begin(), pAa.end(), bya());
sort(pBa.begin(), pBa.end(), bya());
sort(pAb.begin(), pAb.end(), byb());
sort(pBb.begin(), pBb.end(), byb());
dp[0].resize(pAa.size(), -1);
back[0].resize(pAa.size(), -1);
dp[1].resize(pBa.size(), -1);
back[1].resize(pBa.size(), -1);
dp[0][A] = dp[1][B] = 0; //Casos bases
back[0][A] = back[1][B] = 0; //Casos bases
forn(i, A){
aux = resolver(i, 0);
if(aux > res){
res = aux;
a = i;
b = 0;
}
}
forn(i, B){
aux = resolver(i, 1);
if(aux > res){
res = aux;
a = i;
b = 1;
}
}
while(1){ //c marca el avance de a y d marca el avance de b
if(b){ //Si es de B
if(a == B) break;
paux = pAa[back[b][a]];
for(d; pBb[d].b < paux.a; d++){
if(pBb[d].a < pBa[a].a) continue;
rB.push_back(pBb[d].id);
}
a = back[b][a];
b = !b;
} else{ //Si es de A
if(a == A) break;
paux = pBa[back[b][a]];
for(c; pAb[c].b < paux.a; c++){
if(pAb[c].a < pAa[a].a) continue;
rA.push_back(pAb[c].id);
}
a = back[b][a];
b = !b;
}
}
A = rA.size();
B = rB.size();
cout<<res<<"\n";
forn(i, A) cout<<rA[i]<<" "; cout<<"\n";
forn(i, B) cout<<rB[i]<<" "; cout<<"\n";
return 0;
}
Espero que puedan ayudarme, capaz me estoy olvidando algún caso borde o bien mi idea no siempre funciona. Muchas gracias 