# 拼多多笔试 6.16

```#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-26 16:20