[c++] Progr Dinamica [Lis Contest Algoritmi]

[Ca7r]

Buongiorno a tutti!
Spero di risolvere un problema che credo si risolva similmente alla ricerca LIS. VEDASI IL TESTO ALLEGATO
Ma non son sicuro

Codice: Seleziona tutto

#include <string.h>
#include <fstream>
//#include <iostream>
#include <climits>
using namespace std;
typedef struct{
    int x,y,z;
}box;
ifstream in ("in.txt");
ofstream out ("out.txt");
int max_box(box *a, int dim);
int ricbin(box *a, int T[], int l, int r, box elemento);

int main(void) {
  int dim;  
  in >> dim;
  box a[dim];
   for(int j=0; j<dim; j++)
          in >> a[j].x >> a[j].y >> a[j].z;  
  out<< "TOTALE: " << max_box(a, dim)<<endl; 
   return 0;
}
int ricbin(box *a, int T[], int l, int r, box elemento) { 
  int m; 
   while( r - l > 1 ) {
      m = l + (r - l)/2;

      if( a[T[m]].x >= elemento.x && a[T[m]].y >= elemento.y && a[T[m]].z >= elemento.z )
         r = m;
      else
         l = m;
   } 
  return r;
}
 
int max_box(box *a, int dim) {

   int *indicicoda = new int[dim];
   int *indicipreced = new int[dim];
   int lung;
 
   memset(indicicoda, 0, sizeof(indicicoda[0])*dim);
   memset(indicipreced, 0xFF , sizeof(indicipreced[0])*dim); 
 
   indicicoda[0] = 0;
   indicipreced[0] = -1;
   /* punta sempre alla posizione vuota */
   lung = 1; 
   for( int i = 1; i < dim; i++ ) {
      if( a[i].x < a[indicicoda[0]].x &&  a[i].y < a[indicicoda[0]].y && a[i].z < a[indicicoda[0]].z  ) {
         /* se abbiamo un nuovo valore più piccolo */
         indicicoda[0] = i;
      }  else if ( a[i].x > a[indicicoda[lung-1]].x && a[i].y > a[indicicoda[lung-1]].y && a[i].z > a[indicicoda[lung-1]].z ) 
         {
         // a[i] vuole trovare la più grande sottosequenza crescente 
         indicipreced[i] = indicicoda[lung-1];
         indicicoda[lung++] = i;
         }
      else {
          // a[i] potrebbe essere nella sottosequenza finale e quindi potrebbe rimanere in indicicoda 
        int pos = ricbin(a, indicicoda, -1, lung-1, a[i]);
 
        indicipreced[i] = indicicoda[pos-1];
        indicicoda[pos] = i;
      }
   }
   
  /* stampa la sequenza finale risultante, dal più grande intero al più piccolo intero */
   for( int i = indicicoda[lung-1]; i >= 0; i = indicipreced[i] )
      out << a[i].x <<"x"<<a[i].y<<"x"<< a[i].z<<endl; 
   //out << endl;
 
   delete[] indicicoda;
   delete[] indicipreced;
 
   return lung;
}
 

Se in input diamo 3 box:

Codice: Seleziona tutto

3
1 1 1
2 2 2
3 3 3

Allora non ci sono problemi.

Ma se abbiamo input disordinati...

Codice: Seleziona tutto

3
3 3 3
2 2 2
1 1 1

Non va... Dovrebbe restituire lo stesso output di prima perché si inseriscono una dentro l'altra (come nel caso precedente).
Ed il problema è proprio il LIS che non "guarda indietro".
Che modifiche dovrei fare?
SPERO TANTO IN UN VOSTRO AIUTO

[Zoff]

I titoli delle discussioni devono far intuire il problema, per favore modificalo con qualcosa di piu' pertinente e senza maiuscolo.

[Ca7r]

C'é qualcuno? : (