Pagini recente » Cod sursa (job #1075570) | Cod sursa (job #1350457) | Cod sursa (job #826838) | Cod sursa (job #898938) | Cod sursa (job #1923065)
#include <stdio.h>
#define DIM 5001
#define INF 0x3f3f
#define input "subsir2.in"
#define output "subsir2.out"
int N, A[DIM], bst[DIM], T[DIM], rez = INF, poz, min;
char ok[DIM];
void Citire();
void Rezolva();
void Scrie();
int main()
{
Citire();
Rezolva();
Scrie();
return 0;
}
void Citire()
{
int i;
freopen(input, "r", stdin);
freopen(output,"w",stdout);
scanf("%d", &N);
min = INF;
for(i=0; i<N; ++i)
{
scanf("%d", A+i);
if(min<=A[i]) continue;
ok[i] = 1;
min = A[i];
}
}
void Rezolva()
{
int i, j, min;
for(i=N-1; i>=0; --i)
{
bst[i]=min=INF;
T[i] = -1;
for(j=i+1; j<N; ++j)
{
if(A[j]<A[i]) continue;
if(min>A[j]&&(bst[i]>bst[j]+1||(bst[i]==bst[j]+1&&A[j]<A[T[i]])))
bst[i]=bst[j]+1, T[i] = j;
if(min>A[j]) min = A[j];
}
if(bst[i]==INF)
bst[i] = 1, T[i] = i;
if(ok[i] && (rez>bst[i]||(rez==bst[i]&&A[i]<A[poz])))
rez = bst[i], poz = i;
}
}
void Scrie()
{
int i;
printf("%d\n", rez);
for(i=poz;i!=T[i];i=T[i])
printf("%d ", i+1);
printf("%d\n", i+1);
}