拼多多笔试 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");
        // }
    }
}