Pagini recente » Cod sursa (job #1110819) | Cod sursa (job #2273216) | Cod sursa (job #37159) | Cod sursa (job #2125778) | Cod sursa (job #3259403)
#include <fstream>
#define inf 1000000
#define dim 5005
using namespace std;
ifstream f("subsir2.in");
ofstream g("subsir2.out");
int n, k, A[dim], L[dim], T[dim], ok[dim];
void citire()
{
int i, min=inf;
f>>n;
for(i=1; i<=n; i++)
{
f>>A[i];
if( A[i] < min )
{
min = A[i];
ok[i] = 1;
}
}
}
void Solve()
{
int i, j, mn, best=inf, vmin=inf;
for(i=n; i>=1; --i)
{
L[i] = mn = inf;
for(j=i+1; j<=n; ++j)
if( A[j] >= A[i] && A[j] < mn )
{
mn = 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];
k = i;
}
}
}
void afis()
{
g<<L[k]<<'\n';
while( k )
{
g << k << " ";
k = T[k];
}
}
int main()
{
citire();
Solve();
afis();
return 0;
}