Pagini recente » Cod sursa (job #2246714) | Cod sursa (job #1006935)
#include <iostream>
#include <fstream>
using namespace std;
const int Nmax = 5005;
const int oo = 0x3f3f3f3f;
int N;
int V[Nmax];
int D[Nmax], T[Nmax];
int solution = oo, index;
void read()
{
freopen("subsir2.in", "r", stdin);
scanf("%d", &N);
for ( int i = 1; i <= N; ++i )
scanf("%d", &V[i]);
fclose( stdin );
}
void solve()
{
for ( int i = N; i >= 1; i-- )
{
D[i] = oo;
int minim = -1;
for ( int j = i + 1; j <= N; ++j )
{
if ( V[i] <= V[j] )
{
if ( minim == -1 || V[j] < V[minim] )
minim = j;
if ( minim != -1 && ( D[minim] + 1 < D[i] || ( D[minim] + 1 == D[i] && V[minim] < V[ T[i] ] ) ) )
{
D[i] = D[minim] + 1;
T[i] = minim;
}
}
}
if ( D[i] == oo )
D[i] = 1;
}
int minim = -oo;
for ( int i = 1; i <= N; ++i )
{
if ( minim == -oo || V[minim] > V[i] )
minim = i;
if ( minim == i && ( solution > D[i] || ( solution == D[i] && V[i] < V[index] ) ) )
{
solution = D[i];
index = i;
}
}
}
void print()
{
freopen("subsir2.out", "w", stdout);
printf("%d\n", solution);
while ( index != 0 )
{
printf("%d ", index);
index = T[index];
}
fclose( stdout );
}
int main()
{
read();
solve();
print();
return 0;
}