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