| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1091224 | kolorvxl | Giraffes (JOI22_giraffes) | C11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
int n;
int arr[1002];
int cost[1000][1000][1000] = {0};
void apply(int *a, int b) {
if (*a > b) {
*a = b;
}
}
int get_cost(int start, int end, int offset) {
if (end == start) {
return arr[start - 1] != (offset + 1);
}
if (cost[start][end][offset] == -1) {
int length = end - start + 1;
int min = offset + 1;
int max = length + offset;
int costtmp = 10000;
apply(&costtmp, get_cost(start + 1, end, offset + 1) + (min != arr[start- 1]));
apply(&costtmp, get_cost(start + 1, end, offset) + (max != arr[start- 1]));
apply(&costtmp, get_cost(start, end - 1, offset + 1) + (min != arr[end- 1]));
apply(&costtmp, get_cost(start, end - 1, offset) + (max != arr[end- 1]));
cost[start][end][offset] = costtmp;
// printf("%d %d %d %d %d\n", start, end, min, max, costtmp);
}
return cost[start][end][offset];
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
for (int i = 0; i < n + 1; i++) {
for (int j = 0; j < n + 1; j++) {
for (int k = 0; k < n + 1; k++) {
cost[i][j][k] = -1;
}
}
}
printf("%d", get_cost(1, n, 0));
return 0;
}