Pagini recente » Cod sursa (job #2942729) | Cod sursa (job #1976824) | Cod sursa (job #1218772) | Borderou de evaluare (job #3182092) | Cod sursa (job #339502)
Cod sursa(job #339502)
#include <stdio.h>
#define MAX_N 5010
#define inf 2147000000
int n;
int A[MAX_N], c[MAX_N], vine[MAX_N];
void cit() {
freopen("subsir2.in", "r", stdin);
freopen("subsir2.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &A[i]);
}
void solve() {
c[n] = 1; vine[n] = 0;
for (int i = n - 1; i >= 1; i--) {
c[i] = inf;
int val = inf;
for (int j = i + 1; j <= n; j++) {
if (A[j] >= A[i] && A[j] < val) {
val = A[j];
if (c[i] > c[j] + 1) {
c[i] = c[j] + 1;
vine[i] = j;
}
else if (c[i] == c[j] + 1 && A[j] < A[vine[i]])
vine[i] = j;
}
}
}
}
void write() {
int vmin = inf, sol = inf, poz = 0;
for (int i = 1; i <= n; i++)
if (A[i] < vmin) {
if ((c[i] < sol) || (c[i] == sol && A[i] < A[poz])) {
sol = c[i];
poz = i;
}
vmin = A[i];
}
printf("%d\n", sol);
while (poz) {
printf("%d ", poz);
poz = vine[poz];
}
printf("\n");
}
int main() {
cit();
solve();
write();
return 0;
}