拼多多笔试 6.16

总共四道题我就a了第一道。第二题实在是意难平,思路实际上很明确,竟然卡在下表如何表示上,愣是无法开始。

今早洗漱的时候突然就通了,速速写完第二题代码,手动测了几个例子都没啥问题,可惜看不到提交的“通过全部用例”!!!后俩题题目记不住了,太久不写题手生得很。还给面试吗多多,我和你一起吃汉堡。

#include <stdio.h>
#include <stdlib.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int T, N;
    int *P = NULL;
    scanf("%d", &T);

    for (int round = 0; round < T; ++round) {
        int coin, free, sum = 0;
        int i, j;
        scanf("%d", &N);

        P = (int *)malloc(sizeof(int) * N);
        for (i = 0; i < N; ++i) {
            scanf("%d", &P[i]);
            sum += P[i];
        }
        free = (sum - P[N-1]) / 100;

        // 申请 dp[券数][天数] 数组,初始化为0。
        int **dp = (int **)malloc(sizeof(int *) * (free+1));
        for (i = 0; i < free+1; ++i) {
            dp[i] = (int *)malloc(sizeof(int)*N);
        }
        for (i = 0; i < free+1; ++i) {
            for (j = 0; j < N; ++j) {
                dp[i][j] = 0;
            }
        }

        coin = free = 0;
        for (i = 1; i < N; ++i) {
            coin += P[i-1];
            if (coin / 100 == 0) continue;
            if (coin / 100 > free) {
                free = coin / 100;
                for (j = i; j < N; ++j) {
                    dp[free][j] = max(dp[free][j-1], dp[free-1][j-1] + P[j]);
                }
            }
        }
        // 打印省了多少钱
        // printf("%d\n", dp[free][N-1]);
        // 打印最小花费
        printf("%d\n", sum - dp[free][N-1]);
        
        // 打印dp数组
        // for (i = 0; i < free+1; ++i){
        //     for (j = 0; j < N; ++j) {
        //         printf("%3d ", dp[i][j]);
        //     }
        //     printf("\n");
        // }
    }
}

#拼多多笔试#
全部评论
怎么理解呢
点赞
送花
回复 分享
发布于 06-17 22:11 安徽
没看到这批约面的呀
点赞
送花
回复 分享
发布于 06-25 20:38 上海
字节跳动
校招火热招聘中
官网直投

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务