Pagini recente » Cod sursa (job #1420021) | Cod sursa (job #1883592) | Cod sursa (job #1848643) | Cod sursa (job #2684868) | Cod sursa (job #1631336)
#include <fstream>
#include <stack>
using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
const int MAX = 5005;
int a[MAX];
int N;
int D[MAX];
int t[MAX];
int nmax[MAX];
int nmin[MAX];
stack<int> st1, st2;
int indmin;
void Next( int& i, int st, int dr );
int main()
{
int i, j;
fin >> N;
for ( i = 1; i <= N; i++ )
fin >> a[i];
st1.push(N);
st2.push(N);
for ( i = N - 1; i >= 1; i-- )
{
while ( !st1.empty() && a[st1.top()] > a[i] ) st1.pop();
if ( !st1.empty() )
nmin[i] = st1.top();
st1.push(i);
while ( !st2.empty() && a[st2.top()] < a[i] ) st2.pop();
if ( !st2.empty() )
nmax[i] = st2.top();
st2.push(i);
}
D[N] = 1;
for ( i = N - 1; i >= 1; i-- )
{
if ( nmax[i] == 0 )
D[i] = 1;
else
{
j = nmax[i];
D[i] = D[j] + 1;
t[i] = j;
// if ( i == 4 )
// fout << "DA";
for ( Next( j, a[i], a[j] ); j <= N && j != 0; Next( j, a[i], a[j] ) )
if ( D[j] + 1 < D[i] || ( D[j] + 1 == D[i] && a[j] < a[t[i]] ) )
D[i] = D[j] + 1, t[i] = j;
}
}
indmin = 1;
for ( j = 1; j != 0; j = nmin[j] )
if ( D[j] <= D[indmin] )
indmin = j;
fout << D[indmin] << '\n';
for ( i = indmin; i != 0; i = t[i] )
fout << i << ' ';
fin.close();
fout.close();
return 0;
}
void Next( int& i, int st, int dr )
{
int j = i + 1;
while ( !( a[j] >= st && a[j] <= dr ) && j <= N )
j++;
if ( j <= N )
i = j;
else
i = 0;
}