Pagini recente » Cod sursa (job #3285047) | Cod sursa (job #2965481) | Cod sursa (job #674868) | Cod sursa (job #3201986) | Cod sursa (job #2562060)
#include <bits/stdc++.h>
using namespace std;
ifstream fin( "subsir2.in" );
ofstream fout( "subsir2.out" );
const int NMAX = 5005;
int N;
int a[NMAX];
int lis[NMAX];
int pre[NMAX];
bool plpl[NMAX];
void Read()
{
fin >> N;
for( int i = 1; i <= N; ++i )
fin >> a[i];
}
void Do()
{
for( int i = N; i > 0; --i ) {
lis[i] = 1;
pre[i] = i;
for( int j = i + 1; j <= N; ++j )
if( a[i] <= a[j] ) {
plpl[j] = true;
if( lis[i] < lis[j] + 1 || ( lis[i] == lis[j] + 1 && a[j] < a[ pre[i] ] ) ) {
lis[i] = lis[j] + 1;
pre[i] = j;
}
}
else
if( a[i] <= a[j] ) plpl[j] = true;
}
/*for( int i = 1; i <= N; ++i )
fout << a[i] << ' '; fout << '\n';
for( int i = 1; i <= N; ++i )
fout << lis[i] << ' '; fout << '\n';
for( int i = 1; i <= N; ++i )
fout << plpl[i] << ' '; fout << '\n';*/
int lmin = NMAX + 1;
int p;
for( int i = 1; i <= N; ++i )
if( plpl[i] == false ) {
if( lmin > lis[i] || ( lmin == lis[i] && a[i] < a[p] ) ) {
lmin = lis[i];
p = i;
}
}
fout << lmin << '\n';
while( p != pre[p] ) {
fout << p << ' ';
p = pre[p];
}
fout << p;
}
int main()
{
Read();
Do();
return 0;
}