Pagini recente » Cod sursa (job #800189) | Cod sursa (job #1335461) | Cod sursa (job #893196) | Cod sursa (job #1465040) | Cod sursa (job #1769255)
#include <cstdio>
#define NMax 5000
#define INF 1<<30
char atins[NMax+1];
int best[NMax+1];
int fiu[NMax+1];
int a[NMax+1];
int main(){
freopen("subsir2.in","r",stdin);
freopen("subsir2.out","w",stdout);
int i,j,N,lim,ans=INF,first,is;
scanf("%d",&N);
for(i = 1; i <= N; ++i) scanf("%d",&a[i]);
best[N] = 1;
for(i = N-1; i >= 1; --i)
{
best[i] = lim = INF;
for(is = 0, j = i+1; j <= N; ++j)
if( ( a[i] < a[j] && a[j] < lim ) || ( a[i] == a[j] && !is ) )
{
lim = a[j];
atins[j] = 1;
if( best[j]+1 < best[i] ) { best[i] = best[j]+1; fiu[i] = j; }
else if( best[j]+1==best[i] && a[ fiu[i] ] > a[j] ) fiu[i] = j;
if( a[i] == a[j] ) is = 1;
}
if( best[i] == INF ) best[i] = 1;
}
for(i = 1; i <= N; ++i)
if( !atins[i] && ans > best[i] ) { ans = best[i]; first = i; }
else if( !atins[i] && ans == best[i] && a[first] > a[i] ) first = i;
printf("%d\n",ans);
printf("%d ",first);
while(fiu[first])
{
printf("%d ",fiu[first]);
first = fiu[first];
}
return 0;
}