Pagini recente » Cod sursa (job #3131768) | Cod sursa (job #405928) | Cod sursa (job #772942) | Cod sursa (job #782889) | Cod sursa (job #2205891)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iomanip>
#define PI 3.141592653589793
using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
//#define fin cin
//#define fout cout
int dp[5002];
int main(){
int n;
int v[5002], poz[5002], afis[5002];
int crr_max = 0;
int minDP, minDPval;
int DPminTOT = 5002;
int start;
fin >> n;
for( int i = 1 ; i <= n ; ++i ){
fin >> v[i];
}
for( int i = 1 ; i <= n ; ++i ){
minDP = 5002;
minDPval = 1000002;
crr_max = -1000002;
for( int j = i - 1 ; j >= 0 ; --j ){
if( v[j] < v[i] && v[j] > crr_max ){
crr_max = v[j];
if( dp[j] < minDP && v[j] < minDPval ){
minDP = dp[j];
minDPval = v[j];
poz[i] = j;
}
}
}
dp[i] = minDP + 1;
}
crr_max = -1000002;
for( int i = n ; i >= 1 ; --i ){
if( v[i] > crr_max ){
crr_max = v[i];
if( dp[i] < DPminTOT ){
DPminTOT = dp[i];
start = i;
}
}
}
afis[0] = 0;
fout << DPminTOT << "\n";
for( int i = start ; i != 0 ; i = poz[i] ) afis[++afis[0]] = i;
for( int i = afis[0] ; i >= 1 ; --i ) fout << afis[i] << " ";
return 0;
}