P8803 [蓝桥杯 2022 国 B] 费用报销
P8803 [蓝桥杯 2022 国 B] 费用报销 - 洛谷
题目描述
小明在出差结束后返回了公司所在的城市，在填写差旅报销申请时，粗心的小明发现自己弄丢了出差过程中的票据。
为了弥补小明的损失，公司同意小明用别的票据进行报销，但是公司财务要求小明提交的票据中任意两张的日期差不小于 K 天，且总金额不得超过实际差旅用 M。
比如财务要求 K=7 时，若小明提交了一张 1 月 8 日的票据，小明就不能提交 1 月 2 日至 1 月 14 日之间的其他票据，1 月 1 日及之前和 1 月 15 日及之后的票据则可以提交。
公司的同事们一起给小明凑了 N 张票据，小明现在想要请你帮他整理一下，从中选取出符合财务要求的票据，并使总金额尽可能地接近 M。
需要注意，由于这些票据都是同一年的，因此 12 月底的票据不会影响到 1 月初票据的提交。这一年不是闰年。
输入格式
第 1 行：3 个整数，N,M,K。
第 2… N+1 行：每行 3 个整数 mi,di,vi，第 i+1 行表示第 i 张票据时间的月份 mi 和日期 di，vi 表示该票据的面值。
输出格式
第 1 行：1 个整数，表示小明能够凑出的最大报销金额。
输入输出样例
| 输入 #1 | 输出 #1 |
|---|---|
| 4 16 3 1 1 1 1 3 2 1 4 4 1 6 8 | 10 |
说明/提示
【样例说明】
选择 1 月 3 日和 1 月 6 日的票据
【评测用例规模与约定】
对于 100% 的评测用例，1≤N≤1000,1≤M≤5000,1≤K≤50,1≤mi≤12,1≤di≤31,1≤vi≤400
日期保证合法。
蓝桥杯 2022 国赛 B 组 F 题。
思路：
普通dp思路，但是会超时，因为要枚举前驱节点。
代码：
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1005, MAXM=5005;
int n, M, K;
int f[MAXN][MAXM];
struct Bill
{int day, value;
} bills[MAXN];bool cmp(const Bill &a, const Bill &b)
{return a.day < b.day;
}int monthDays[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};int toDay(int m, int d)
{int res = 0;for(int i=1; i<m; i++) res += monthDays[i];return res + d;
}int main()
{cin >> n >> M >> K;for(int i=1; i<=n; i++) {int m, d, v;cin >> m >> d >> v;bills[i].day = toDay(m,d);bills[i].value = v;}sort(bills+1, bills+n+1, cmp);for(int i=1; i<=n; i++) {for(int j=0; j<=M; j++) {f[i][j] = f[i-1][j];if(j >= bills[i].value) {for(int k=0; k<i; k++) {if(bills[i].day - bills[k].day >= K) {f[i][j] = max(f[i][j], f[k][j-bills[i].value] + bills[i].value);}}}}}cout << f[n][M] << endl;return 0;
}
思路：
预处理前驱结点
代码：
#include<bits/stdc++.h>
using namespace std;int n, m, i, j, ans, k, sum;struct BillNode {int m, d, v, t; // 月份、日期、价值、时间戳
}bills[1005];int dp[1005][5005], monthDays[1005], last[1005];bool compare(BillNode a, BillNode b) {return a.t < b.t;
}int daysInMonth[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m >> k;// 计算各月累计天数for(i = 2; i <= 12; i++) monthDays[i] = monthDays[i-1] + daysInMonth[i-1];// 输入账单数据并计算时间戳for(i = 1; i <= n; i++) {cin >> bills[i].m >> bills[i].d >> bills[i].v;bills[i].t = monthDays[bills[i].m] + bills[i].d;}// 按时间排序sort(bills+1, bills+1+n, compare);// 预处理每个账单的前一个有效账单for(i = 1; i <= n; i++) {for(j = 0; j < i; j++) {if(bills[i].t - bills[j].t >= k) last[i] = j;}}// 动态规划求解for(i = 1; i <= n; i++) {for(j = m; j >= bills[i].v; j--) {dp[i][j] = dp[i-1][j];dp[i][j] = max(dp[i][j], dp[last[i]][j-bills[i].v] + bills[i].v);}}cout << dp[n][m];return 0;
}
