Pagini recente » Cod sursa (job #2365702) | Cod sursa (job #2782192)
#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin( "subsir2.in" );
ofstream fout( "subsir2.out" );
const int MAXN = 5005;
const int INF = (int)1e6 + 1;
int v[MAXN], ok_last[MAXN];
int dp[MAXN], pre[MAXN];
vector<int> sol;
int main() {
int n, mx = -INF;
fin >> n;
for ( int i = 1; i <= n; ++i ) {
fin >> v[i];
}
for ( int i = n; i >= 1; --i ) {
ok_last[i] = (v[i] > mx);
mx = max( mx, v[i] );
}
for ( int i = 1; i <= n; ++i ) {
mx = -INF;
int pos = i, val = INF;
for ( int j = i - 1; j >= 1; --j ) {
if ( v[j] <= v[i] && mx < v[j] ) {
if ( val > dp[j] + 1 ) {
val = dp[j] + 1;
pos = j;
} else if ( val == dp[j] + 1 && v[pos] > v[j] ) {
pos = j;
}
}
if ( v[j] <= v[i] ) {
mx = max( mx, v[j] );
}
}
dp[i] = val;
pre[i] = pos;
if ( dp[i] == INF ) {
dp[i] = 1;
}
}
int res = INF, ind = 0;
for ( int i = 1; i <= n; ++i ) {
if ( ok_last[i] ) {
if ( res > dp[i] ) {
res = dp[i];
ind = i;
} else if ( res == dp[i] && v[ind] > v[i] ) {
ind = i;
}
}
}
fout << res << "\n";
while ( pre[ind] != ind ) {
sol.push_back( ind );
ind = pre[ind];
}
sol.push_back( ind );
for ( int i = sol.size() - 1; i >= 0; --i ) {
fout << sol[i] << " ";
}
fin.close();
fout.close();
return 0;
}