Cod sursa(job #764756)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 6 iulie 2012 10:25:55
Problema Secv Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
#define INF 2147000000
int v[5002],d[5001],a[5001],c[5001];
int main ()
{
	int n,i,l,min,ultim,j;
	ifstream f("secv.in");
	ofstream g("secv.out");
	f>>n;
	for(i=1;i<=n;i++)
		f>>v[i];
	f.close();
	for(i=1;i<=n;i++)
		a[i]=v[i];
	sort(a+1,a+n+1);
	for(i=1,l=0;i<=n;i++) {
		c[++l]=a[i];
		while((a[i]==a[i+1])&&(i<=n))
			i++;
	}
	for(i=1;i<=n;i++)
		if(v[i]==c[l])
			d[i]=1;
	d[n+1]=INF;
	for(j=l-1;j>=1;j--) {
		ultim=n+1;
		for(i=n;i>=1;i--) {
			if(v[i]==c[j])
				d[i]=d[ultim]+ultim-i;
			if(v[i]==c[j+1])
				ultim=i;
		}
	}
	min=INF;
	for(i=1;i<=n;i++)
		if((v[i]==c[1])&&(d[i]<min))
			min=d[i];
	if(min>=INF)
		g<<"-1";
	else g<<min;
	g.close();
	return 0;
}