Pagini recente » Cod sursa (job #27794) | Cod sursa (job #921896) | Cod sursa (job #1265571) | Cod sursa (job #1906242) | Cod sursa (job #1766367)
#include<fstream>
#include<algorithm>
#include<map>
using namespace std;
ifstream fin ("subsir2.in"); ofstream fout ("subsir2.out");
const int nmax = 5000;
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 == 0) {
return ;
}
afis(r[ pos ]);
fout << 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 mx = -inf;
for (int i = 1; i <= n; ++ i) {
v[ i ] = aux[ v[ i ] ];
d[ i ] = inf;
mx = -inf;
for (int j = i - 1; j >= 0; -- j) {
if (v[ j ] <= v[ i ] && mx < 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;
}
mx = v[ j ];
}
}
}
mx = -inf;
for (int i = n; i > 0; -- i) {
if (mx >= v[ i ]) {
d[ i ] = inf;
} else {
mx = 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;
}