Pagini recente » Cod sursa (job #570966) | Cod sursa (job #182829) | Cod sursa (job #1532466) | Cod sursa (job #2103691) | Cod sursa (job #16106)
Cod sursa(job #16106)
#include<stdio.h>
#define dim 5005
#define inf 0x3f3f3f3f
long V[dim], Min=inf; int N, A[dim], T[dim], ok[dim];
void read();
void dynamics();
void write();
int main()
{
read();
dynamics();
write();
return 0;
}
void read()
{
freopen("subsir2.in", "r", stdin);
scanf("%d", &N);
int i;
for(i=1; i<=N; ++i)
{
scanf("%ld", V+i);
if(V[i] < Min)
{
Min = V[i];
ok[i] = 1;
}
}
fclose(stdin);
}
void dynamics()
{
int i, j, amin; long min;
A[N] = 1; T[N] = 0;
for(i=N-1; i; --i)
{
min = inf;
amin = N<<1;
for(j=i+1; j<=N; ++j)
if(V[j] <= min && V[j] >= V[i])
{
if( A[j]+1 < amin )
{
amin = A[j]+1;
A[i] = A[j]+1;
T[i] = j;
}
if(A[j]+1 == amin && V[j] < min)
{
min = V[j];
T[i] = j;
}
}
if( !A[i] )
{
A[i] = 1;
T[i] = 0;
}
}
}
void write()
{
freopen("subsir2.out", "w", stdout);
int i, p, amin = N<<1; Min = inf;
for(i=1; i<=N; ++i)
if( ok[i] && A[i] < amin )
{
amin = A[i];
Min = V[i];
p = i;
}
else if( ok[i] && A[i] == amin && V[i] <= Min )
{
Min = V[i];
p = i;
}
printf("%d\n", A[p]);
while(p)
{
printf("%d ", p);
p = T[p];
}
fclose(stdout);
}