Pagini recente » Cod sursa (job #2255875) | Cod sursa (job #2808271) | Cod sursa (job #1908595) | Cod sursa (job #1214046) | Cod sursa (job #1558877)
#include <stdio.h>
#include <limits.h>
#define Nadejde 5000
int N;
int d[Nadejde + 1];
int val[Nadejde + 1];
int parent[Nadejde + 1];
int main(void) {
int i, j, pos, min, curr;
FILE *f = fopen("subsir2.in", "r");
/* Citirea datelor. */
fscanf(f, "%d", &N);
for (i = 1; i <= N; i++) {
fscanf(f, "%d", &val[i]);
}
val[0] = INT_MIN;
fclose(f);
/* Calcularea solutiei. */
for (i = N; i >= 0; i--) {
min = d[i] = INT_MAX;
for (j = i + 1; j <= N; j++) {
if ((val[j] < min) && (val[i] <= val[j])) {
min = val[j];
curr = d[j] + 1;
/* Cautam minimul lexicografic. */
if ((d[i] == curr) && (val[j] < val[parent[i]])) {
parent[i] = j;
}
if (curr < d[i]) {
d[i] = curr;
parent[i] = j;
}
}
}
if (d[i] == INT_MAX) {
d[i] = 1;
parent[i] = i;
}
}
/* Afisarea solutiei. */
freopen("subsir2.out", "w", stdout);
fprintf(stdout, "%d\n", d[0] - 1);
for (pos = 0; pos != parent[pos]; pos = parent[pos]) {
printf("%d ", parent[pos]);
}
fclose(stdout);
/// Multumim Doamne!
puts("Doamne ajuta!");
return 0;
}