Pagini recente » Cod sursa (job #1684461) | Cod sursa (job #1644828) | Cod sursa (job #83976) | Cod sursa (job #171175) | Cod sursa (job #16192)
Cod sursa(job #16192)
#include <cstdio>
#define dim 5005
#define inf 0x3f3f3f
int N, P, A[dim], L[dim], T[dim], ok[dim];
void Read_data();
void Solve();
void Write();
int main()
{
Read_data();
Solve();
Write();
return 0;
}
void Read_data()
{
freopen("subsir2.in", "r", stdin);
scanf("%d", &N);
int i, min=inf;
for(i=1; i<=N; ++i)
{
scanf("%d", A+i);
if( A[i] < min )
{
min = A[i];
ok[i] = 1;
}
}
fclose(stdin);
}
void Solve()
{
int i, j, min, best=inf, Vmin=inf;
for(i=N; i>=1; --i)
{
L[i] = min = inf;
for(j=i+1; j<=N; ++j)
if( A[j] >= A[i] && A[j] < min )
{
min = A[j];
if( L[j]+1 < L[i] )
{
L[i] = L[j]+1;
T[i] = j;
}
else if( L[j]+1 == L[i] && A[j] < A[T[i]] )
T[i] = j;
}
if( !T[i] ) L[i] = 1;
if( ok[i])
if( L[i] < best || L[i] == best && A[i] < Vmin )
{
best = L[i];
Vmin = A[i];
P = i;
}
}
}
void Write()
{
freopen("subsir2.out", "w", stdout);
printf("%d\n", L[P]);
while( P )
{
printf("%d ", P);
P = T[P];
}
fclose(stdout);
}