#include <stdio.h>
int n;
int arr[1002];
int cost[1002][1002][1002] = {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;
}
Compilation message
giraffes.c: In function 'main':
giraffes.c:39:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
39 | scanf("%d", &n);
| ^~~~~~~~~~~~~~~
giraffes.c:41:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | scanf("%d", &arr[i]);
| ^~~~~~~~~~~~~~~~~~~~
/usr/lib/gcc/x86_64-linux-gnu/10/../../../x86_64-linux-gnu/libc.a(assert.o): in function `__assert_fail_base':
(.text+0x114): relocation truncated to fit: R_X86_64_PC32 against symbol `__abort_msg' defined in .bss section in /usr/lib/gcc/x86_64-linux-gnu/10/../../../x86_64-linux-gnu/libc.a(abort.o)
/usr/lib/gcc/x86_64-linux-gnu/10/../../../x86_64-linux-gnu/libc.a(loadmsgcat.o): in function `_nl_load_domain':
(.text+0x3c): relocation truncated to fit: R_X86_64_PC32 against `.bss'
(.text+0x5a): relocation truncated to fit: R_X86_64_PC32 against `.bss'
(.text+0x61): relocation truncated to fit: R_X86_64_PC32 against `.bss'
(.text+0x67): relocation truncated to fit: R_X86_64_PC32 against `.bss'
(.text+0x73): relocation truncated to fit: R_X86_64_PC32 against `.bss'
(.text+0x48a): relocation truncated to fit: R_X86_64_PC32 against `.bss'
(.text+0x4a1): relocation truncated to fit: R_X86_64_PC32 against `.bss'
(.text+0x4ac): relocation truncated to fit: R_X86_64_PC32 against `.bss'
(.text+0x4c2): relocation truncated to fit: R_X86_64_PC32 against `.bss'
(.text+0x510): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status
