专栏文章

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

OOKC__THUNDER
P8803题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mip5jdxy
此快照首次捕获于
2025/12/03 06:30
3 个月前
此快照最后确认于
2025/12/03 06:30
3 个月前
查看原文

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

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

本题方法：01 背包 DP

本题为 01 背包 DP，只需进行预处理即可。
好，我们开始，一步一步解释吧：

输入预处理

由于题目中每张票据输入的是对应的月、日，所以我们应把日期变为当日是今年的第几天。
首先是预处理数组：
CPP
int ycl[22]={0,31,59,90,120,151,181,212,243,273,304,334,365},gsw[1111],dp[1111][5555];//gsw也是一个预处理数组，后续使用
其中 ycliycl_i 是指当日期的月份 mimi 为 i+1i+1 时，全年前 ii 个月共有多少天。所以只需再加上第 i+1i+1 月的日子 didi 就能完成输入预处理。
CPP
struct P{int r,v;}a[1111];//r日期，v为面值
为了方便后续排序，使用结构体将每张票据的信息合并到一起。
输入：
CPP
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;//见上
}
进一步预处理：
CPP
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;//见下
这里是要将排完序的数组预处理。根据题目，小明提交的票据中任意两张的日期差应不小于 kk 天，而后续 DP 中的 i−1i-1 无法满足条件，故使用数组 gswgsw，来记录第 ii 张票据之前最大的满足条件的票据 jj。

01 背包 DP

正常 01 背包 DP 即可。
CPP
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 代码：

CPP
#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^

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...