题解：P8803 [蓝桥杯 2022 国 B] 费用报销

· · 题解

P8803[蓝桥杯2022国B]费用报销 题解

废话部分：这是本蒟蒻第二篇题解，第一篇在小号上。

本题方法：01 背包 DP

本题为 01 背包 DP，只需进行预处理即可。

好，我们开始，一步一步解释吧：

输入预处理

由于题目中每张票据输入的是对应的月、日，所以我们应把日期变为当日是今年的第几天。

首先是预处理数组：

int ycl[22]={0,31,59,90,120,151,181,212,243,273,304,334,365},gsw[1111],dp[1111][5555];//gsw也是一个预处理数组，后续使用

其中 ycl_i 是指当日期的月份 mi 为 i+1 时，全年前 i 个月共有多少天。所以只需再加上第 i+1 月的日子 di 就能完成输入预处理。

struct P{int r,v;}a[1111];//r日期，v为面值

为了方便后续排序，使用结构体将每张票据的信息合并到一起。

输入：

int n,m,k;
cin>>n>>m>>k;//题目要求
for(int i=1;i<=n;i++)
{
    int mi,di;
    cin>>mi>>di>>a[i].v;
    a[i].r=ycl[mi-1]+di;//见上
}

进一步预处理：

sort(a+1,a+n+1,cmp);//排个序
for(int i=1;i<=n;i++) for(int j=0;j<i;j++) if(a[i].r-a[j].r>=k) gsw[i]=j;//见下

这里是要将排完序的数组预处理。根据题目，小明提交的票据中任意两张的日期差应不小于 k 天，而后续 DP 中的 i-1 无法满足条件，故使用数组 gsw，来记录第 i 张票据之前最大的满足条件的票据 j。

01 背包 DP

正常 01 背包 DP 即可。

for(int i=1;i<=n;i++)//二维01背包，dp[i][j]代表第i张票据，当最大可装价值为j时，可凑出的最大金额
{
  for(int j=0;j<=m;j++)
  {
    dp[i][j]=dp[i-1][j];
    if(j>=e[i].v) dp[i][j]=max(dp[i][j],dp[gsw[i]][j-e[i].v]+e[i].v);//不要忘了用gsw
  }
}
cout<<dp[n][m];

祭出 AC 记录和 AC 代码：

#include<bits/stdc++.h>
using namespace std;
struct P{int r,v;}a[1111];
int ycl[22]={0,31,59,90,120,151,181,212,243,273,304,334,365},gsw[1111],dp[1111][5555];
bool cmp(P x,P y){return x.r<y.r;}
int main()
{
    int n,m,k,mx=0;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        int mi,di;
        cin>>mi>>di>>a[i].v;
        a[i].r=ycl[mi-1]+di;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++) for(int j=0;j<i;j++) if(a[i].r-a[j].r>=k) gsw[i]=j;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            dp[i][j]=dp[i-1][j];
            if(j>=a[i].v) dp[i][j]=max(dp[i][j],dp[gsw[i]][j-a[i].v]+a[i].v);
        }
    }
    cout<<dp[n][m];
    return 0;
}

希望管理员通过 ^o^