Pagini recente » Cod sursa (job #3183482) | Cod sursa (job #912132) | Cod sursa (job #1476782) | Cod sursa (job #924794) | Cod sursa (job #2676855)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
int n, v[5005], lung, p[5005], dp[5005];
int main(){
fin >> n;
for (int i = 1; i <= n; ++i){
fin >> v[i];
}
dp[n] = 1;
p[n] = -1;
for (int i = n - 1; i >= 1; --i){
dp[i] = 1e9;
int maxx = 1e9;
bool gasit = false;
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]){
if (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[n] = -1;
}
}
int minim = v[1], minimdp = dp[1], pos = 1;
for (int i = 2; i <= n; ++i){
if (v[i] < minim){
if (dp[i] < minimdp){
minimdp = dp[i];
pos = i;
}
else if (dp[i] == minim){
if (v[i] < minim){
minim = v[i];
pos = i;
}
}
}
minim = min(minim, v[i]);
}
fout << minimdp << "\n";
while (pos != -1){
fout << pos << " ";
pos = p[pos];
}
fin.close();
fout.close();
return 0;
}