Cod sursa(job #1737630)

Utilizator Andrei_CotorAndrei Cotor Andrei_Cotor Data 4 august 2016 15:16:41
Problema Subsir 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream>
#define INF 1000000000
using namespace std;
ifstream fi("subsir2.in");
ofstream fo("subsir2.out");
int n,i,A[5001],j,B[5001],C[5001],nr,minim;
int main()
{
    fi>>n;
    for(i=1; i<=n; i++)
    {
        fi>>A[i];
    }
    A[0]=-INF;
    for(i=n; i>=0; i--)
    {
        minim=INF;
        B[i]=INF;
        for(j=i+1; j<=n; j++)
        {
            if (A[j]<minim && A[j]>=A[i])
            {
                minim=A[j];
                if(B[i]>B[j]+1)
                {
                    B[i]=B[j]+1;
                    C[i]=j;
                }
                else
                    if (B[i]==B[j]+1 && A[j]<A[C[i]])
                        C[i]=j;
            }
            if(B[i]==INF)
            {
                B[i]=1;
                C[i]=i;
            }
        }
    }
    fo<<B[0]-1<<"\n";
    i=0;
    nr=B[0]-1;
    while(C[i]!=i)
    {
        nr--;
        fo<<C[i]<<" ";
        i=C[i];
    }
    fo<<"\n";
    fi.close();
    fo.close();
    return 0;
}