Cod sursa(job #7767)

Utilizator crawlerPuni Andrei Paul crawler Data 22 ianuarie 2007 17:01:25
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include<stdio.h>
#define fin "subsir2.in"
#define fout "subsir2.out"
#define NMAX 5001
#define INF 20000001
long n,min,start,v[NMAX],a[NMAX],b[NMAX],c[NMAX];
//a bun ; b lungime ; c reconst 
FILE *in,*out;

void print(long p) {
	
	if (c[p]==p) {
		out=fopen(fout,"a");
		fprintf(out,"%ld\n%ld",min,p);
	       	fclose(out);	
	}
	else {
		print(c[p]);
		out=fopen(fout,"a");
		fprintf(out," %ld",p);	
		fclose(out);
		
	}

}
int main() {
long i,j,k,best;
	
	in=fopen(fin,"r");  

	fscanf(in,"%ld",&n);

	for (i=1;i<=n;i++) fscanf(in,"%ld",&v[i]);

	min=NMAX;

	for (i=n;i>0;i--) {

		k=INF; best=INF; a[i]=1; c[i]=i;	

	 	for (j=i+1;j<=n;j++) 
			
			if (v[j]<k && v[i]<=v[j]) {
				
				a[j]=0;
				
				if (b[j]<best) {

					best=b[j];

					c[i]=j; 
				}
				
				if (v[j]<k) k=v[j];

				if (b[j]==best && v[j]<v[c[i]]) c[i]=j; 	
			}


		if (best==INF) b[i]=1;

		else b[i]=best+1;
		
	}	

	out=fopen(fout,"w");	

	//for (i=1;i<=n;i++) fprintf(out,"%ld ",a[i]);
	
	for (i=1;i<=n;i++) 

		if (a[i])  

			if (min>b[i]) {
				
				min=b[i];
				start=i;

			}

			else 
				if (min==b[i] && v[i]<v[start]) start=i;
	
	fprintf(out,"%ld\n",min);
	
	do {

		fprintf(out,"%ld ",start);
		
		start=c[start]; 

	} while (c[start]!=start);
	
	fprintf(out,"%ld\n",start);

	fclose(in); fclose(out);	
	
return 0;
}