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.样例输出
10
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.原题链接
费用报销
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];
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;
}
}
}
|