Pagini recente » Cod sursa (job #2269954) | Cod sursa (job #1666407) | Cod sursa (job #1942725) | Cod sursa (job #1061893) | Cod sursa (job #764756)
Cod sursa(job #764756)
#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;
}