diff options
author | Iru Cai <mytbk920423@gmail.com> | 2018-06-11 16:46:43 +0800 |
---|---|---|
committer | Iru Cai <mytbk920423@gmail.com> | 2018-06-11 16:46:43 +0800 |
commit | 9920a766c17402a58fc4457d2fc643cc7905e684 (patch) | |
tree | b966224ecba3cefbd11a74ad1f996dd1e35ee115 /euler345.c | |
parent | 7f25c6fc31b376ca1ed0f4c183ef4d232b6ee2b5 (diff) | |
download | project_euler-9920a766c17402a58fc4457d2fc643cc7905e684.tar.xz |
112, 345-347
Diffstat (limited to 'euler345.c')
-rw-r--r-- | euler345.c | 67 |
1 files changed, 67 insertions, 0 deletions
diff --git a/euler345.c b/euler345.c new file mode 100644 index 0000000..b598981 --- /dev/null +++ b/euler345.c @@ -0,0 +1,67 @@ +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +int mxsum(int **m, int n, int d, int visited[]) +{ + int ans; + int sel = -1; + if (d == n) + return 0; + + /* select the biggest of the line first */ + for (int i = 0; i < n; i++) { + if (!visited[i]) { + if (sel == -1) + sel = i; + else if (m[d][i] > m[d][sel]) + sel = i; + } + } + visited[sel] = 1; + ans = m[d][sel] + mxsum(m, n, d+1, visited); + visited[sel] = 0; + + for (int i = 0; i < n; i++) { + if (visited[i] || i == sel) + continue; + visited[i] = 1; + int t = m[d][i]; + /* estimate the maximum value of remaining numbers */ + int re = 0; + for (int j = d+1; j < n; j++) { + int linemax = 0; + for (int k = 0; k < n; k++) { + if (!visited[k] && m[j][k] > linemax) + linemax = m[j][k]; + } + re += linemax; + } + if (t + re > ans) { + t += mxsum(m, n, d+1, visited); + } + visited[i] = 0; + if (t > ans) + ans = t; + } + return ans; +} + +int main() +{ + int n; + int **m; + int visited[15]; + + scanf("%d", &n); + m = (int**)malloc(sizeof(int*) * n); + memset(visited, 0, sizeof(visited)); + for (int i = 0; i < n; i++) { + m[i] = (int*)malloc(sizeof(int) * n); + for (int j = 0; j < n; j++) { + scanf("%d", &m[i][j]); + } + } + + printf("%d\n", mxsum(m, n, 0, visited)); +} |