Pagini recente » Cod sursa (job #2147163) | Cod sursa (job #1145139) | Cod sursa (job #2414790) | Cod sursa (job #2149950) | Cod sursa (job #17425)
Cod sursa(job #17425)
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> rel[5001];
int ch[5001];
int maxc;
int sir[5001];
int lmin;
int asd;
int n;
bool cmpf( const int &a, const int &b )
{
if ( sir[a] < sir[b] ) return 1;
return 0;
}
int main()
{
int i,j;
freopen("subsir2.in","r",stdin);
freopen("subsir2.out","w",stdout);
scanf("%d\n", &n);
for ( i = 1; i <= n; i++ )
scanf("%d ", &sir[i] );
for ( i = n; i >= 1; i-- )
{
maxc = 10000000;
ch[i]=1;
for ( j = i+1; j <= n; j++ )
{
if ( sir[j] < maxc )
{
if ( sir[j] > sir[i] )
{
if ( ch[j]+1 < ch[i] || ch[i] == 1)
{
ch[i]= ch[j]+1;
rel[i].clear();
rel[i].push_back(j);
}
else if ( ch[j] + 1 == ch[i] )
rel[i].push_back(j);
maxc = sir[j];
}
}
}
sort( rel[i].begin(), rel[i].end(), cmpf );
}
maxc = sir[1];
lmin = 1000000;
for ( i = 1; i <= n; i++ )
{
if ( maxc >= sir[i] )
{
if ( ch[i]<lmin ) lmin = ch[i];
maxc = sir[i];
}
}
asd = sir[1];
sir[0] = 999990000;
maxc = 0;
for ( i = 1; i <= n; i ++ )
if ( asd >= sir[i] )
{
if ( ch[i] == lmin ) if ( sir[maxc] > sir[i] ) maxc = i;
asd = sir[i];
}
printf("%d\n", lmin);
printf("%d", maxc);
while ( rel[maxc].size() )
{
printf(" %d", rel[maxc][0]);
maxc = rel[maxc][0];
}
fclose(stdin);
fclose(stdout);
return 0;
}