蓝桥杯 2022 国 B 费用报销

P8803 [蓝桥杯 2022 国 B] 费用报销 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

小明在出差结束后返回了公司所在的城市，在填写差旅报销申请时，粗心的小明发现自己弄丢了出差过程中的票据。

为了弥补小明的损失，公司同意小明用别的票据进行报销，但是公司财务要求小明提交的票据中任意两张的日期差不小于 $K$ 天，且总金额不得超过实际差旅费用 $M$。

比如财务要求 $K=7$ 时，若小明提交了一张 1 月 8 日的票据，小明就不能提交 1 月 2 日至 1 月 14 日之间的其他票据，1 月 1 日及之前和 1 月 15 日及之后的票据则可以提交。

公司的同事们一起给小明凑了 $N$ 张票据，小明现在想要请你帮他整理一下，从中选取出符合财务要求的票据, 并使总金额尽可能接近 $M$ 。

需要注意，由于这些票据都是同一年的，因此 12 月底的票据不会影响到 1 月初票据的提交。这一年不是闰年。

输入格式

第 $1$ 行：$3$ 个整数, $N,M,K$。

第 $2\dots N+1$ 行：每行 3 个整数 $m_i,d_i,v_i$, 第 $i+1$ 行表示第 $i$ 张票据时间的月份 $m_i$ 和日期 $d_i$，$v_i$ 表示该票据的面值。

输出格式

第 $1$ 行：$1$ 个整数, 表示小明能够凑出的最大报销金额。

样例 #1

样例输入 #1

4 16 3
1 1 1
1 3 2
1 4 4
1 6 8

样例输出 #1

10

提示

【样例说明】

选择 1 月 3 日和 1 月 6 日的票据

【评测用例规模与约定】

对于 $100\%$ 的评测用例, $1\le N\le 1000,1\le M\le 5000,1\le K\le 50,1\le m_i\le$ $12,1\le d_i\le 31,1\le v_i\le 400$

日期保证合法。

蓝桥杯 2022 国赛 B 组 F 题。

思路

给你一些带有价值v的物品, 每个物品有日期, 当选择 $i$ 天的物品时, $(i-k,i+k)$ 区间内的物品将不能被选择。求一种最大的选择方案, 使得最终价值尽可能接近 $m$。

考虑一种无后效性的DP顺序, 这里就是对于当前物品的日期 $i$, 只考虑 $(-\infty ,i-k]$ 区间内的物品来转移。这点解决之后就是一个有 $n$ 个物品, 背包容量为 $m$ 的01背包了, 注意此时不是用到 $i-1$ 无法使用滚动数组优化, 总时间复杂度为 $O(nm)=O(5e6)$ 可以通过。

自己写这道题的时候走了点弯路, 设了一个 $day[365]$ 代表日期在 $i$ 天的物品价值, 且同一天给累加一块, 但是一个 $k$ 区间内只能选择一个票据, 故WA。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 10;
int month[] = {0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365};
int f[N][N];
int last[N];
 
struct Day
{
    int d, v;
    bool operator<(const Day &w)
    {
        return d < w.d;
    }
} day[N];
 
void solve()
{
 
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
    {
        int m, d, v;
        cin >> m >> d >> v;
        int days = month[m - 1] + d;
        day[i] = {days, v};
    }
 
    sort(day + 1, day + 1 + n);
    
    for (int i = 1; i <= n; i++)
        for (int j = 1; j < i; j++)
            if (day[i].d - day[j].d >= k)
                last[i] = j;
    
    f[0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= m; j++)
        {
            f[i][j] = f[i - 1][j];
            if (j >= day[i].v)
                f[i][j] |= f[last[i]][j - day[i].v];
        }
    }
 
    for (int i = m; i >= 0; i--)
        if (f[n][i])
        {
            cout << i << endl;
            break;
        }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}