Cod sursa(job #1957023)

Utilizator mateibanuBanu Matei Costin mateibanu Data 7 aprilie 2017 11:45:03
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <stdio.h>

using namespace std;

#define INF 2*10e9+1
#define MAX 5005

int v[MAX],l[MAX],nxt[MAX],t[MAX];

FILE*f=fopen("subsir2.in","r");
FILE*g=fopen("subsir2.out","w");

int main()
{
    int n,i,p,j,mn;
    fscanf(f,"%d",&n);
    v[0]=INF;
    for (i=1;i<=n;i++){
        fscanf(f,"%d",&v[i]);
    }
    l[0]=INF;
    for (i=n;i>=1;i--){
        mn=INF;
        p=0;
        for (j=i+1;j<=n;j++){
            if (v[j]<mn&&v[j]>=v[i]&&(l[j]<l[p]||(l[j]==l[p]&&v[j]<v[p]))) {p=j;}
            if (v[j]>=v[i]) t[j]=1;
            if (v[j]<mn&&v[j]>=v[i]) mn=v[j];
        }
        if (p){
            l[i]=l[p]+1;
            nxt[i]=p;
        }
        else {
            nxt[i]=n+1;
            l[i]=1;
        }
    }
    mn=0;
    for (i=1;i<=n;i++){
        if (!t[i]&&(l[i]<l[mn]||(l[i]==l[mn]&&v[i]<v[mn]))) mn=i;
        l[nxt[i]]=INF;
    }
    fprintf(g,"%d\n",l[mn]);
    while (mn<=n){
        fprintf(g,"%d ",mn);
        mn=nxt[mn];
    }
    fclose(f);
    fclose(g);
    return 0;
}