Cod sursa(job #496459)

Utilizator ConsstantinTabacu Raul Consstantin Data 29 octombrie 2010 11:13:25
Problema Subsir 2 Scor 64
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<stdio.h>
int val[ 5005 ],ant[ 5005 ],l[ 5005 ],i,j,k,n;

void citire(){
freopen("subsir2.in","r",stdin);
scanf("%d",&n);
for(i=1;i<=n;i++)
	scanf("%d",&val[i]);
}
void solve(){
int Min;
for(i = n-1;i>=1;i--){
	Min = 1<<30;
	for(j = i+1;j<=n;j++)
	if(val[i] <= val[j])
	{
		if(val[j] < Min) Min = val[j];
		
		if(val[j] <= Min)
			{if(l[j]+1 < l[i] || !l[i])
				{l[i] = l[j]+1;
				ant[i] = j;
				}
			else
			if(l[j] + 1 == l[i] && val[j] < val[ant[i]])
				ant[i] = j;
			}
		}
	}
k = 1;
Min =val[1] ;
for( i = 2 ; i<= n ; i++)
	{if(val[i] < Min)Min = val[i];
	if(val[i] == Min && l[i] < l[k] )
		k=i;
	else
	if(val[i] == Min && l[i] == l[k] && val[i] < val[k] )
		k = i;
	}
}

void afisare(){
freopen("subsir2.out","w",stdout);

printf("%d\n",l[k]+1);

do
	{printf("%d ",k);
	k = ant[k];
	}
while(k != 0);
}
int main(){
citire();
solve();
afisare();
return 0;}