Cod sursa(job #340479)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 14 august 2009 20:02:07
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <vector>
#include <fstream>
using namespace std;
#define pb push_back
const int NMAX=5005;
const int Inf=2000000;
int N,x[NMAX],din[NMAX],nxt[NMAX],Sol[NMAX];
vector<int> a,b;
ifstream f("subsir2.in");
ofstream g("subsir2.out");
int main()
{
    int i,j,k,lmin=Inf,least;
    f>>N;
    for (i=1;i<=N;++i) f>>x[i];
    din[N]=1;
    for (i=N-1;i>0;--i)
    {
        least=Inf;
        din[i]=Inf;
        for (j=i+1;j<=N;++j)
          if (x[j] >= x[i] && least > x[j])
          {
             least=x[j];
             if (din[j]+1 < din[i])
             {
                din[i]=din[j]+1;
                nxt[i]=j;
             }
             else
             if (din[j]+1 == din[i])
               if (x[j] < x[nxt[i]])
                 nxt[i]=j;
          }
        if (least == Inf) din[i]=1;
    }
    least=Inf;
    for (i=1;i<=N;++i)
      if (x[i] < least)
      {
        least=x[i];
        lmin=min(lmin,din[i]);
      }
    g<<lmin<<'\n';
    a.reserve(lmin);
    b.reserve(lmin);
    a=vector<int>(lmin,Inf);
    least=Inf;
    for (i=1;i<=N;++i)
      if (x[i] < least)
      {
        least=x[i];
        if (lmin == din[i])
        {
           k=0;
           for (j=i;j;j=nxt[j]) b[k++]=x[j];
           if (a > b)
           {
               b=a;
               k=0;
               for (j=i;j;j=nxt[j]) Sol[++k]=j;
           }
        }
      }
    for (i=1;i<=lmin;++i) g<<Sol[i]<<' ';
    return 0;
}