From be6678fbca007e73d69c9a9c5cddb8241a987149 Mon Sep 17 00:00:00 2001 From: Nguyễn Gia Phong Date: Mon, 15 Jul 2019 19:58:48 +0700 Subject: So I gave up on a number theory one --- codechef/cirmerge.c | 32 ++++++++++++++++++++++++++++++++ 1 file changed, 32 insertions(+) create mode 100644 codechef/cirmerge.c (limited to 'codechef/cirmerge.c') diff --git a/codechef/cirmerge.c b/codechef/cirmerge.c new file mode 100644 index 0000000..678f47a --- /dev/null +++ b/codechef/cirmerge.c @@ -0,0 +1,32 @@ +#include + +int main() +{ + int t, n, i, j, k; + long long tmp, a[400][400], p[400][400] = {}; + + for (scanf("%d", &t); t--; printf("%lld\n", tmp)) { + scanf("%d", &n); + for (i = 0; i < n; ++i) + scanf("%lld", *a + i); + + for (i = 1; i < n; ++i) + for (j = 0; j < n; ++j) { + p[i][j] = p[i-1][j]; + for (k = 1; k < i; ++k) { + tmp = p[k-1][j] + p[i-k][(j+k)%n]; + if (tmp < p[i][j]) + p[i][j] = tmp; + } + p[i][j] += a[i][j] = a[i-1][j] + a[0][(i+j)%n]; + } + + long long *m = p[n-1]; + tmp = *m; + for (i = 1; i < n; ++i) + if (m[i] < tmp) + tmp = m[i]; + } + + return 0; +} -- cgit 1.4.1