Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
1.7 kB
5
Indexable
Never
# include<stdio.h>
# include <limits.h>
# include <math.h>

int N,S,T;
int h[15+1];
int jumped[15+1];   // 記錄石頭是否被跳過
int color[15+1];    // 記錄石頭顏色
int route[15];      // 記錄跳的路徑
int max_e = INT_MIN;
int max_j = INT_MIN;

void jump(int cur, int end, int step);
int cost(int jumps);

void jump(int cur, int end, int step){
    int i;
    for(i=1;i<=N;i++){  // for i in 全部石頭
        if(color[i]==color[cur] || i==cur-1 || i==cur+1){   //若顏色相同 or 為當前石頭的前後一個石頭
            if(jumped[i]==1 && i!=cur){     // 且並非已跳過的石頭 or 不是自己
                route[step] = i;    // 記錄跳到的石頭編號
                jumped[cur] = 0;    // 跳之前的石頭變為 0
                jump(i, end, step+1);   // 進行下一次跳躍
            }
        }
    }
    if(cur>=end){
        if(cur==end){
            int cur_e = 0;
            cur_e = cost(step-1);
            if(cur_e>max_e){
                max_e = cur_e;
                max_j = step-1;
            }
            else if(cur_e=max_e && step-1>max_j){
                max_j = step-1;
            }
        }
        return;
    }
}

int cost(int jumps){
    int i;
    int total_e = 0;
    for(i=0;i<jumps;i++){
        total_e += abs(route[i]-route[i+1])*abs(h[route[i]]- h[route[i+1]]);
    }
    return total_e;
}

int main(void){
    int i;
    scanf("%d%d%d", &N, &S, &T);
    route[0] = S;
    for(i=1;i<=N;i++)   scanf("%d", &h[i]);
    for(i=1;i<=N;i++)   scanf("%d", &color[i]);
    for(i=1;i<=N;i++)   jumped[i] = 1;
    jump(S, T, 1);
    printf("%d %d\n", max_e, max_j);
    return 0;
}