Pagini recente » Monitorul de evaluare | Istoria paginii utilizator/dursinaalexandru | Cod sursa (job #1809969) | Atasamentele paginii Clasament simulare-oji-matei-2 | Cod sursa (job #1043145)
#include <fstream>
using namespace std;
ifstream cin("subsir2.in");
ofstream cout("subsir2.out");
const int nmax = 5002;
int n;
int a[nmax], dp[nmax], who[nmax];
int vmin = int(2e9);
void readData() {
cin >> n;
for (int i = 1;i <= n;i++) {
cin >> a[i];
}
}
void solve() {
int bstPos = n + 1;
dp[n + 1] = n;
for (int i = n;i >= 1;i--) {
who[i] = i;
dp[i] = n + 1;
vmin = min(vmin,a[i]);
int aux = int(2e9);
for(int j = i + 1;j <= n;j++) {
if (a[j] >= a[i]) {
aux = min(aux,a[j]);
if (aux == a[j]) {
if (dp[j] + 1 < dp[i] || (dp[j] + 1 == dp[i] && a[who[i]] > a[j])) {
dp[i] = dp[j] + 1;
who[i] = j;
}
}
}
}
if (dp[i] == n + 1) dp[i] = 1;
if (a[i] == vmin) {
bstPos = i;
}
}
cout << dp[bstPos] << "\n";
while (bstPos != who[bstPos]) {
cout << bstPos << " ";
bstPos = who[bstPos];
}
cout << bstPos;
}
int main()
{
readData();
solve();
return 0;
}