第十三届蓝桥杯C++B组国赛F题——费用报销（AC）

叁歲伎倆 2023-09-28 23:21 7阅读 0赞

#### 目录 ####

*  1.费用报销
 *   *  1.问题描述
     *  2.输入格式
     *  3.输出格式
     *  4.样例输入
     *  5.样例输出
     *  6.数据范围
     *  7.原题链接
 *  2.解题思路
 *  3. AC\_code

## 1.费用报销 ##

### 1.问题描述 ###

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

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

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

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

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

### 2.输入格式 ###

第  1 1 1 行： 3 个整数,  N , M , K N, M, K N,M,K  
第  2 … N + 1 2 \\ldots N+1 2…N\+1 行: 每行 3 个整数  m i , d i , v i m\_\{i\}, d\_\{i\}, v\_\{i\} mi,di,vi, 第  i + 1 i+1 i\+1 行表示第  i i i 张票据时间 的月份  m i m\_\{i\} mi 和日期  d i , v i d\_\{i\}, v\_\{i\} di,vi表示该票据的面值

### 3.输出格式 ###

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

### 4.样例输入 ###

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

### 5.样例输出 ###

### 6.数据范围 ###

1 ≤ N ≤ 1000 , 1 ≤ M ≤ 5000 , 1 ≤ K ≤ 50 , 1 ≤ m i ≤ 12 , 1 ≤ d i ≤ 31 , 1 ≤ v i ≤ 40012 , 1 ≤ d i ≤ 31 , 1 ≤ v i ≤ 400 1≤N≤1000,1≤M≤5000,1≤K≤50,1≤m i≤ 12,1 \\leq d\_\{i\} \\leq 31,1 \\leq v\_\{i\} \\leq 40012,1≤di ≤31,1≤vi≤400 1≤N≤1000,1≤M≤5000,1≤K≤50,1≤mi≤12,1≤di≤31,1≤vi≤40012,1≤di≤31,1≤vi≤400

### 7.原题链接 ###

[费用报销][Link 1]

## 2.解题思路 ##

这是一道比较明显的`01`背包问题，涉及物品的选择。这些票据都有月份和天数，为了方便比较，我们将其全部转换为天数，使用`pair`存下天数和票额，然后根据天数来进行排序。

定义`bool`数组`f[i][j]`，含义为**只考虑前i个物品，能否组成价值为j的情况**。当我们枚举到票据`i`时，假设它的天数为  x x x，如果我们选了票据`i`，那么票据日期 \[ x − k , x \] \[x-k,x\] \[x−k,x\]都是不可取的。所以我们需要使用双指针维护每一个票据`i`上一个和他日期相差大于`k`天的票据`l`。

接下来进行状态转移的分析，当 j < t \[ i \] . s e c o n d j<t\[i\].second j<t\[i\].second（表示排序后第  i i i 个票据的价值），说明我们的票据价值太大，无法选择，转化为背包思想就是我们的物品太重背包放不下。此时状态转移就为 f \[ i \] \[ j \] = f \[ i − 1 \] \[ j \] f\[i\]\[j\]=f\[i-1\]\[j\] f\[i\]\[j\]=f\[i−1\]\[j\]。当 j > = t \[ i \] . s e c o n d j>=t\[i\].second j>=t\[i\].second时，说明当前票据我们是可选的，我们有两种抉择——**选还是不选**？如果我们不选择它，那么转移方程同上。如果我们选择它，那么状态转移时就**不一定**是从上一个物品转移过来，题意要求两件任意的两张票据需要至少间隔`k`天，我们应该从上一张比当前票据至少少`k`天的票据`l`转移过来，那么状态转移方程为： f \[ i − 1 \] \[ j \] ∣ f \[ l \] \[ j − t \[ i \] . s e c o n d \] f\[i-1\]\[j\] | f\[l\]\[j-t\[i\].second\] f\[i−1\]\[j\]∣f\[l\]\[j−t\[i\].second\]。

将转移方程结合起来，上面是可选状态，下面是不可选状态:  
 f \[ i \] \[ j \] = \{ f \[ i − 1 \] \[ j \] if j<t\[i\].second f \[ i − 1 \] \[ j \] ∣ f \[ l \] \[ j − t \[ i \] . s e c o n d \] if j>=t\[i\].secode f\[i\]\[j\]= \\begin\{cases\} f\[i-1\]\[j\] &\\text\{if j<t\[i\].second\}\\\\ f\[i-1\]\[j\] | f\[l\]\[j-t\[i\].second\] &\\text\{if j>=t\[i\].secode\}\\\\ \\end\{cases\} f\[i\]\[j\]=\{ f\[i−1\]\[j\]f\[i−1\]\[j\]∣f\[l\]\[j−t\[i\].second\]if j<t\[i\].secondif j>=t\[i\].secode

当然因为是`01`背包问题，我们也可以使用滚动数组优化，这里为了方便大家理解就没有进行优化。最后从最大体积  M M M 倒着遍历体积  V V V，那么第一个  d p \[ n \] \[ V \] = t r u e dp\[n\]\[V\] = true dp\[n\]\[V\]=true 对应的  V V V 即为答案。

时间复杂度: O ( n m ) O(nm) O(nm)。

## 3. AC\_code ##

#include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    typedef pair<int,int> PII;;
    const int N=1010;
    
    int n,m,k;
    int w[]={
        0,31,28,31,30,31,30,31,31,30,31,30,31};
    PII t[N];
    //只考虑前i个物品能否组成体积为j的情况
    bool f[N][5*N];
    int main() 
    {
        
    	for(int i=1;i<=12;++i) w[i]+=w[i-1];
    	scanf("%d%d%d",&n,&m,&k);
    	for(int i=1;i<=n;++i){
        
    		int a,b,c;
    		scanf("%d%d%d",&a,&b,&c);
    		t[i]={
        w[a-1]+b,c};
    	}
    	//按日期排序
    	sort(t+1,t+n+1);
    	f[0][0]=true;
    	//双指针
    	int l=0;
    	for(int i=1;i<=n;++i){
        
    		//找到上一个可选的票据
    		while(t[i].first-t[l+1].first>=k) l++;
    		for(int j=0;j<=m;++j){
        
    			f[i][j]=f[i-1][j];
    			if(j>=t[i].second) f[i][j]|=f[l][j-t[i].second];
    		}
    	}
    	for(int v=m;v>=0;--v){
        
    		if(f[n][v]){
        
    			printf("%d\n",v);
    			return 0;
    		}
    	}
    }

[Link 1]: https://www.lanqiao.cn/problems/2195/learning/