当前位置：首页 > article >正文

蓝桥杯每日真题 - 第19天

article 2024/11/23 2:28:21

题目：（费用报销）

题目描述（13届 C&C++ B组F题）

解题思路：

1. 问题抽象

本问题可以看作一个限制条件较多的优化问题，核心是如何在金额和时间约束下选择最优方案：

动态规划是理想的解决方法。
我们定义 dp[i] 为到第 i 天为止的最大报销金额。

2. 日期统一化

为了方便处理时间差，需将日期（月份和天数）统一转化为一年中的第几天。例如：

1 月 1 日为第 1 天；
2 月 1 日为第 32 天（31+1）。

这一步能让日期差的计算简单且高效。

3. 动态规划状态转移

状态表示：dp[i] 表示到第 i 天为止的最大报销金额。
转移方程：对每张票据：
- 如果报销当前票据：dp[i] = max(dp[i-1], dp[pre] + v[i])，其中 pre = i - K。
- 如果不报销当前票据：dp[i] = dp[i-1]。

4. 优化思路

按票据日期排序，确保动态规划时的时间顺序正确。
动态更新 dp 数组，逐步累积最大金额。

代码实现（C语言）：

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

typedef struct {
  int day, v;
} dps;

int N, M, K;
int m[1009], d[1009];
dps dp[1009];
int a[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int p[366] = {0};

// 计算每月对应的天数累计和
int month(int mi) {
  int sum = 0;
  for (int i = 0; i < mi - 1; i++) sum += a[i];
  return sum;
}

// 将日期统一成一年中的第几天
void becomeday() {
  for (int i = 0; i < N; i++) {
    dp[i].day = month(m[i]) + d[i];
    p[dp[i].day] = dp[i].v;
  }
}

// 比较函数，用于qsort排序
int cmp(const void *a1, const void *a2) {
  dps s1 = *(dps *)a1;
  dps s2 = *(dps *)a2;
  return s1.day - s2.day;
}

int main() {
  scanf("%d%d%d", &N, &M, &K);
  for (int i = 0; i < N; i++) {
    scanf("%d%d%d", &m[i], &d[i], &dp[i].v);
  }
  
  // 转换日期并排序
  becomeday();
  qsort(dp, N, sizeof(dp[0]), cmp);
  
  // 动态规划
  for (int i = 1; i < 366; i++) {
    int pre = i - K >= 0 ? i - K : 0;
    if (p[i] + p[pre] <= M) {
      p[i] = p[i] + p[pre] > p[i - 1] ? p[i] + p[pre] : p[i - 1];
    } else {
      p[i] = p[i - 1];
    }
  }
  
  printf("%d", p[365]);
  return 0;
}