Pagini recente » Cod sursa (job #754395) | Cod sursa (job #2747821) | Cod sursa (job #1244243) | Cod sursa (job #1707299) | Cod sursa (job #339503)
Cod sursa(job #339503)
#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;
}
}
if (c[i] == inf) c[i] = 1;
}
}
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;
}