Pagini recente » Cod sursa (job #2358551) | Cod sursa (job #816605) | Cod sursa (job #2905533) | Cod sursa (job #2782199)
#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_first[MAXN];
int dp[MAXN], nxt[MAXN];
int main() {
int n, mn = INF;
fin >> n;
for ( int i = 1; i <= n; ++i ) {
fin >> v[i];
}
for ( int i = 1; i <= n; ++i ) {
ok_first[i] = (v[i] < mn);
mn = min( mn, v[i] );
}
for ( int i = n; i >= 1; --i ) {
mn = INF;
int pos = i, val = INF;
for ( int j = i + 1; j <= n; ++j ) {
if ( v[i] <= v[j] && mn > 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[i] <= v[j] ) {
mn = min( mn, v[j] );
}
}
dp[i] = val;
nxt[i] = pos;
if ( dp[i] == INF ) {
dp[i] = 1;
}
}
int res = INF, ind = 1;
for ( int i = 1; i <= n; ++i ) {
if ( ok_first[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 ( nxt[ind] != ind ) {
fout << ind << " ";
ind = nxt[ind];
}
fout << ind << " ";
fin.close();
fout.close();
return 0;
}