2023华为od机试C卷【跳格子3】C语言 实现_跳格子c语言

目录

题目

思路

Code

题目

小明和朋友们一起玩跳格子游戏，每个格子上有特定的分数score =  [1 -1-6 7 -17 7]，从起点score[0]开始，每次最大的步长为k，请你返回小明跳到终点score[n-1]时，能得到的最大得分。
注
格子的总长度和步长的区间在[1，100000]
每个格了的分数在[-10000,10000]区间中

输入描述
6//第一行输入总的格了数量
1 -1 -6 7 -17 7/第二行输入每个格子的分数score[i]
2//第三行输入最大跳的步长k

输出描述：

一个整数代表最大得分。

示例1：

输入：

6
1 -1 -6 7 -17 7
2
输出：

14

思路

1：这题还是一个很久没考到过的动态规划类的题目。

2：其实状态转移方程还是比较好推导的cache[i] = max(cache[i-k] ~cache[i-1]) + score[i]，有一个优化的点就是我们可以用一个队列来保存其中cache[i-k]~cache[i-1]的最大值。

Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>
#include <limits.h>
#include <float.h>
#include <regex.h>
#include <ctype.h>
 
#define CEILING_POS(X) ((X-(int)(X)) > 0 ? (int)(X+1) : (int)(X))
#define CEILING_NEG(X) ((X-(int)(X)) < 0 ? (int)(X-1) : (int)(X))
#define CEILING(X) ( ((X) > 0) ? CEILING_POS(X) : CEILING_NEG(X) )
 
#define MIN(a, b) ((a) < (b)) ? (a) : (b)
#define MAX(a, b) ((a) > (b)) ? (a) : (b)
 
int cmpfunc_str (const void * a, const void * b) {
   return strcmp(a ,b);
}
 
int cmpfunc (const void * a, const void * b) {
   return ( *(int*)a - *(int*)b );
}
//qsort(dp, m+1, sizeof(int), cmpfunc);
 
/*
char input[200000];
    fgets(input, 200000, stdin);
 
    //逗号分隔
    char* token = strtok(input, ",");
    int v[1000];
    int score1 = 0;
    while (token != NULL) {
        v[score1++] = atoi(token);
        token = strtok(NULL, ",");
    }*/
 
int cmp(const void *a,const void *b)
{
    int *ap = (int *)a;       
    int *bp = (int *)b;
 
    if(bp[0] == ap[0]){
        return ap[1]>bp[1];
    } else {
        return ap[0]>bp[0];
    }
} 
//qsort(a, n, sizeof(a[0]), cmp);
 
 
int main() {
    char input1[200];
    fgets(input1, 200, stdin);
    int n= atoi(input1);
 
    char input[200000];
    fgets(input, 200000, stdin);
    char* token = strtok(input, " ");
    int nums[1000];
    int count = 0;
    while (token != NULL) {
        nums[count++] = atoi(token);
        token = strtok(NULL, " ");
    }
 
    char input2[200];
    fgets(input2, 200, stdin);
    int k = atoi(input2);
 
    int queue[n][2];
    int cache[n];
    for (int i = 0; i < n; i++) {
        queue[i][0] = 0;
        queue[i][1] = 0;
        cache[i] = 0;
    }
    cache[0] = nums[0];
    queue[0][0] = 0;
    queue[0][1] = cache[0];
    int index1 = 0;
    int index2 = 1;
 
    int i=1;
    while(true){
        if(i>=n){
            break;
        } else {
            while(index1<index2){
                if(queue[index1][0] < i - k){
                    index1 +=1;
                } else {
                    break;
                }
            }
            cache[i] = nums[i] + queue[index1][1];
 
            while(index1<index2){
                if(queue[index1][1] <= cache[i]){
                    index1 +=1;
                }else {
                    break;
                }
            }
 
            queue[index2][0] = i;
            queue[index2][1] = cache[i];
            index2+=1;
        }
        i+=1;
    }
    printf("%d", cache[n - 1]);
    return 0;
}

【华为od机试真题Python+JS+Java合集】【超值优惠】：Py/JS/Java合集

【华为od机试真题Python】：Python真题题库

【华为od机试真题JavaScript】：JavaScript真题题库

【华为od机试真题Java】：Java真题题库

【华为od机试真题C++】：C++真题题库

【华为od机试真题C语言】：C语言真题题库

【华为od面试手撕代码题库】：面试手撕代码题库

【华为od机试面试交流群：830285880】