Cod sursa(job #1206924)

Utilizator sddddgjdZloteanu Anastasia sddddgjd Data 11 iulie 2014 15:18:27
Problema Subsir 2 Scor 73
Compilator c Status done
Runda Arhiva de probleme Marime 0.9 kb
#include<stdio.h>
#define N 5000
int v[N+2],lg[N+2],prev[N+2];
int main()
{
    FILE *fin,*fout;
    fin=fopen("subsir2.in","r");
    fout=fopen("subsir2.out","w");
    int n,i;
    fscanf(fin,"%d",&n);
    for(i=1; i<=n; i++)
        fscanf(fin,"%d",&v[i]);
    n++;
    v[0]=-1000000,v[n]=1000000;
    for(i=0; i<=n; i++)
        prev[i]=-1;
    for(i=n-1; i>=0; i--)
    {
        lg[i]=N+1;
        int min=10000001,j;
        for(j=i+1; j<=n; j++)
            if(v[j]>=v[i]&&v[j]<min)
            {
                if(lg[i]>=lg[j])
                    lg[i]=lg[j]+1,prev[i]=j;
                else if(lg[i]==lg[j]+1&&v[i]<v[prev[i]])
                    prev[i]=j;
                min=v[j];
            }
    }
    fprintf(fout,"%d\n",lg[0]-1);
    int poz=0;
    while(prev[poz]!=n)
    {
        fprintf(fout,"%d ",prev[poz]);
        poz=prev[poz];
    }
    return 0;
}