Pagini recente » Cod sursa (job #780422) | Istoria paginii runda/wettbewerbssimulation1/clasament | Cod sursa (job #2070295) | Istoria paginii runda/orange_morning | Cod sursa (job #339266)
Cod sursa(job #339266)
#include <stdio.h>
#include <algorithm>
using namespace std;
#define MAX_N 5010
#define inf 2147000000
int n, sol;
int A[MAX_N], c[MAX_N], vine[MAX_N], val[MAX_N];
int sir[MAX_N], fin[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 reconst();
void solve() {
//c[i] = lungimea celui mai scurt subsir crescator maximal cu capul dr in i
for (int i = n; i >= 1; i--) {
c[i] = inf;
val[i] = max(val[i + 1], A[i]);
}
for (int i = 0; i < n; i++) {
int p = inf;
for (int j = i + 1; j <= n; j++)
if (A[j] >= A[i] && A[j] < p) {
if (c[j] > c[i] + 1) {
c[j] = c[i] + 1;
vine[j] = i;
}
else
if (c[j] == c[i] + 1 && A[i] < A[vine[j]])
vine[j] = i;
p = A[j];
}
}
reconst();
}
void reconst() {
sol = inf;
for (int i = 1; i <= n; i++) {
if (c[i] < sol && val[i + 1] < A[i])
sol = c[i];
fin[i] = 0;
}
A[0] = inf;
/* for (int i = 1; i <= n; i++)
if (c[i] == sol && val[i + 1] < A[i]) {
int k = i, nr = sol;
while (k) {
sir[nr--] = k;
k = vine[k];
}
int comp = 0;
for (int j = 1; j <= sol; j++) {
if (A[sir[j]] < A[fin[j]]) {
comp = 1;
break;
}
if (A[sir[j]] > A[fin[j]]) {
comp = -1;
break;
}
}
if (comp)
for (int j = 1; j <= sol; j++)
fin[j] = sir[j];
} */
}
void write() {
printf("%d\n", sol);
for (int i = 1; i <= sol; i++)
printf("%d ", fin[i]);
printf("\n");
}
int main() {
cit();
solve();
write();
return 0;
}