Pagini recente » Cod sursa (job #2272152) | Cod sursa (job #2813129) | Cod sursa (job #153126) | Cod sursa (job #1061890) | Cod sursa (job #1766439)
#include<fstream>
#include<algorithm>
#include<map>
using namespace std;
ifstream fin ("subsir2.in"); ofstream fout ("subsir2.out");
const int nmax = 5005;
const int inf = 1 << 30;
int n;
int v[nmax + 1], d[nmax + 1], r[nmax + 1];
map< int, int > aux;
void afis (int pos) {
if (pos == n + 1) {
return ;
}
fout << pos << " ";
afis(r[ pos ]);
}
int main() {
fin >> n;
for (int i = 1; i <= n; ++ i) {
fin >> v[ i ];
aux[ v[ i ] ] = 0;
}
int ind = 1;
for (map< int, int >::iterator it = aux.begin(); it != aux.end(); ++ it) {
it -> second = ind ++;
}
int mn = inf;
v[n + 1] = inf - 1;
for (int i = n; i > 0; -- i) {
v[ i ] = aux[ v[ i ] ];
d[ i ] = inf;
mn = inf;
for (int j = i + 1; j <= n + 1; ++ j) {
if (v[ j ] >= v[ i ] && mn > v[ j ]) {
if (d[ i ] > d[ j ] + 1 || (d[ i ] == d[ j ] + 1 && v[ j ] < v[ r[ i ] ])) {
d[ i ] = d[ j ] + 1;
r[ i ] = j;
}
mn = v[ j ];
}
}
}
mn = inf;
for (int i = 1; i <= n; ++ i) {
if (mn <= v[ i ]) {
d[ i ] = inf;
} else {
mn = v[ i ];
}
}
int sol = 1;
for (int i = 2; i <= n; ++ i) {
if (d[ i ] < d[ sol ] || (d[ i ] == d[ sol ] && v[ sol ] > v[ i ])) {
sol = i;
}
}
fout << d[ sol ] << "\n";
afis( sol );
fin.close();
fout.close();
return 0;
}