Cod sursa(job #1206886)

Utilizator sddddgjdZloteanu Anastasia sddddgjd Data 11 iulie 2014 13:46:59
Problema Subsir 2 Scor 4
Compilator c Status done
Runda Arhiva de probleme Marime 1.59 kb
#include<stdio.h>
#define N 5000
int v[N],prev[N],start[N],lg[N],ans[N],canExt[N];
int main(){
    FILE *fin,*fout;
    fin=fopen("subsir2.in","r");
    fout=fopen("subsir2.out","w");
    int n,i;
    fscanf(fin,"%d",&n);
    for(i=0;i<n;i++){
        fscanf(fin,"%d",&v[i]);
        prev[i]=-1;
        start[i]=v[i];
        lg[i]=1;
    }
    for(i=0;i<n;i++){
        int j,lgInit=lg[i];
        for(j=i-1;j>=0;j--){
            if(v[j]<=v[i]&&(lgInit+lg[j]<=lg[i]||(lgInit+lg[j]==lg[i]&&start[j]<start[i])||lgInit==lg[i])){
                start[i]=start[j];
                prev[i]=j;
                lg[i]=lgInit+lg[j];
            }
            if(v[j]<=v[i])
                canExt[j]=1;
        }
    }
    int min=999999,poz=0;
    for(i=0;i<n;i++){
        if(canExt[i]==0&&(lg[i]<min||(start[i]<start[poz]&&lg[i]==min))){
            poz=i;
            min=lg[i];
        }
        else
            if(lg[i]==min&&canExt[i]==0){
                int lastDif=1,poz1=poz,poz2=i;
                while(poz1!=-1){
                    if(v[poz1]<v[poz2])
                        lastDif=1;
                    else
                        if(v[poz2]<v[poz1])
                            lastDif=2;
                    poz1=prev[poz1];
                    poz2=prev[poz2];
                }
                if(lastDif==2)
                    poz=i;
            }
    }
    fprintf(fout,"%d\n",min);
    int c=min;
    while(poz!=-1){
        ans[--min]=poz;
        poz=prev[poz];
    }
    for(i=0;i<c;i++)
        fprintf(fout,"%d ",ans[i]+1);
    return 0;
}