Submission #70997535

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <inttypes.h>
int N;
int64_t a[512];
int64_t sum[512];
int64_t memo[512][512];
/* [s, e] */
int64_t calc(int s, int e) {
  int64_t ans = 0, i;
  if (s == e) return 0;
  if (memo[s][e]) return ~memo[s][e];
  for (i = s; i < e; i++) {
    int64_t candidate = calc(s, i) + calc(i + 1, e) + (sum[e] - sum[s - 1]);
    if (i == s || candidate < ans) ans = candidate;
  }
  return ~(memo[s][e] = ~ans);
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <inttypes.h>

int N;
int64_t a[512];

int64_t sum[512];

int64_t memo[512][512];

/* [s, e] */
int64_t calc(int s, int e) {
	int64_t ans = 0, i;
	if (s == e) return 0;
	if (memo[s][e]) return ~memo[s][e];
	for (i = s; i < e; i++) {
		int64_t candidate = calc(s, i) + calc(i + 1, e) + (sum[e] - sum[s - 1]);
		if (i == s || candidate < ans) ans = candidate;
	}
	return ~(memo[s][e] = ~ans);
}

int main(void) {
	int i;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 1; i <= N; i++) {
		if (scanf("%" SCNd64, &a[i]) != 1) return 1;
		sum[i] = sum[i - 1] + a[i];
	}
	printf("%" PRId64 "\n", calc(1, N));
	return 0;
}

Submission Info

Judge Result