Pagini recente » Cod sursa (job #2942563) | Cod sursa (job #970248) | Cod sursa (job #2602571) | Cod sursa (job #908166) | Cod sursa (job #2676863)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
const int nmax = 5005;
int n, v[nmax], dp[nmax], p[nmax];
int main(){
fin >> n;
for (int i = 1; i <= n; ++i){
fin >> v[i];
}
for (int i = n; i >= 1; --i){
dp[i] = 1e9;
bool gasit = false;
int maxx = 1e9;
for (int j = i + 1; j <= n; ++j){
if (v[j] >= v[i] && maxx > v[j]){
if (1 + dp[j] < dp[i]){
dp[i] = 1 + dp[j];
p[i] = j;
}
else if (1 + dp[j] == dp[i] && v[j] < v[p[i]]){
p[i] = j;
}
gasit = true;
}
if (v[j] >= v[i]) maxx = min(maxx, v[j]);
}
if (!gasit){
dp[i] = 1;
p[i] = -1;
}
}
int maxx = 1e9, minim = 1e9, pos, val;
for (int i = 1; i <= n; ++i){
if (maxx < v[i]){
continue;
}
if (dp[i] < minim){
minim = dp[i];
pos = i;
val = v[i];
}
else if (dp[i] == minim){
if (v[i] < val){
val = v[i];
pos = i;
}
}
maxx = min(maxx, v[i]);
}
fout << minim << "\n";
while (pos != -1){
fout << pos << " ";
pos = p[pos];
}
fin.close();
fout.close();
return 0;
}