Created
November 3, 2023 15:19
-
-
Save hsuan1117/84944413a7a975e5532bf263382fcad9 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include<stdio.h> | |
#include<stdlib.h> | |
#define N 15+3 | |
int n, s, t; | |
int jumped[N] = {0}; | |
int color[N] = {0}; | |
int height[N] = {0}; | |
int cango(int from, int to) { | |
if ((to >= 0 && to < n) && (from - 1 == to || from + 1 == to || color[from] == color[to]) && jumped[to] == 0) { | |
return 1; | |
} | |
return 0; | |
} | |
int M = -1; | |
int C = -1; | |
int pre[N] = {0}; | |
int calc(int from, int to) { | |
if (from == -1) return 0; | |
int d = (to - from); | |
if (d < 0) d = -d; | |
int h = height[from] - height[to]; | |
if (h < 0) h = -h; | |
return d * h; | |
} | |
void dfs(int from, int x, int prev, int cnt) { | |
pre[x] = from; | |
// printf("from: %d, to: %d, prev: %d\n", from + 1, x + 1, prev); | |
int nx = x - 1; | |
if (cango(x, nx)) { | |
jumped[x] = 1; | |
dfs(x, nx, prev + calc(x, nx), cnt + 1); | |
jumped[x] = 0; | |
} | |
nx = x + 1; | |
if (cango(x, nx)) { | |
jumped[x] = 1; | |
dfs(x, nx, prev + calc(x, nx), cnt + 1); | |
jumped[x] = 0; | |
} | |
for (int i = 0; i < n; i++) { | |
jumped[x] = 1; | |
if (color[i] == color[x] && i != x && cango(x, i)) { | |
nx = i; | |
dfs(x, nx, prev + calc(x, nx), cnt + 1); | |
} | |
jumped[x] = 0; | |
} | |
if (x == t) { | |
// printf("[LEAF]: from: %d, to: %d, prev: %d, cnt: %d\n", from + 1, x + 1, prev, cnt); | |
//the path | |
// int p = x; | |
// while (p != -1) { | |
// printf("%d ", p + 1); | |
// p = pre[p]; | |
// } | |
// printf("\n"); | |
if (prev > M) { | |
M = prev; | |
C = cnt; | |
} | |
} | |
} | |
signed main() { | |
scanf("%d %d %d", &n, &s, &t); | |
s--; | |
t--; | |
for (int i = 0; i < n; i++) { | |
int d; | |
scanf(" %d", &d); | |
height[i] = d; | |
} | |
for (int i = 0; i < n; i++) { | |
int d; | |
scanf(" %d", &d); | |
color[i] = d; | |
} | |
dfs(-1, s, 0, 0); | |
printf("%d %d\n", M, C ); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment