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 \ldots 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 \leq N \leq 1000,1 \leq M \leq 5000,1 \leq K \leq 50,1 \leq m_{i} \leq$ $12,1 \leq d_{i} \leq 31,1 \leq v_{i} \leq 400$

日期保证合法。

蓝桥杯 2022 国赛 B 组 F 题。

很裸的一道01背包问题

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;

#define x first
#define y second

const int N = 1e3 + 10;
const int M = 5e3 + 10;

int n, m, k;
int month[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int sum_month[13];
bool dp[N][M];
PII bill[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> k;
    for (int i = 1; i <= 12; i ++ ) sum_month[i] = sum_month[i - 1] + month[i];

    for (int i = 1; i <= n; i ++ )
    {
        int mon, d, v;
        cin >> mon >> d >> v;

        bill[i] = {sum_month[mon - 1] + d, v};
    }

    sort(bill + 1, bill + n + 1);

    dp[0][0] = true;

//  cout << 1 << endl;
//  return 0;
    int last_bill = 0;
    for (int i = 1; i <= n; i ++ )
    {
        while (bill[i].x - bill[last_bill + 1].x >= k) last_bill ++ ; 
        for (int j = 0; j <= m; j ++ )
        {
            dp[i][j] = dp[i - 1][j];
            if (j >= bill[i].y) dp[i][j] |= dp[last_bill][j - bill[i].y];
        }
    }   

//  return 0;
    for (int i = m; i >= 0; i -- )
        if (dp[n][i])
        {
            cout << i << endl;
            return 0; 
        }


    return 0;
}