Mai intai trebuie sa te autentifici.
Cod sursa(job #339501)
Utilizator | Data | 10 august 2009 09:35:07 | |
---|---|---|---|
Problema | Subsir 2 | Scor | 57 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.94 kb |
#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) {
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;
}