建设双语的网站,wordpress批量插件,app和小程序的开发成本,wordpress 收费主题下载费用报销
问题描述
小明在出差结束后返回了公司所在的城市, 在填写差旅报销申请时, 粗心 的小明发现自己弄丢了出差过程中的票据。
为了弥补小明的损失, 公司同意小明用别的票据进行报销, 但是公司财务 要求小明提交的票据中任意两张的日期差不小于 K 天, 且总金额不得超过实…费用报销
问题描述
小明在出差结束后返回了公司所在的城市, 在填写差旅报销申请时, 粗心 的小明发现自己弄丢了出差过程中的票据。
为了弥补小明的损失, 公司同意小明用别的票据进行报销, 但是公司财务 要求小明提交的票据中任意两张的日期差不小于 K 天, 且总金额不得超过实际 差旅费用 M 。
比如财务要求 K7 时, 若小明提交了一张 1 月 8 日的票据, 小明就不能 提交 1 月 2 日至 1 月 14 日之间的其他票据, 1 月 1 日及之前和 1 月 15 日及之 后的票据则可以提交。
公司的同事们一起给小明凑了 N 张票据, 小明现在想要请你帮他整理一 下, 从中选取出符合财务要求的票据, 并使总金额尽可能接近 M 。
需要注意, 由于这些票据都是同一年的, 因此 12 月底的票据不会影响到 1 月初票据的提交。这一年不是闰年。
输入格式
第 1 行 3 个整数, N,M,K
第 2…N1 行: 每行 3 个整数 mi,di,vi, 第 i1 行表示第 i 张票据时间 的月份mi 和日期 di,vi 表示该票据的面值
输出格式
第 1 行: 1 个整数, 表示小明能够凑出的最大报销金额
样例输入
4 16 3
1 1 1
1 3 2
1 4 4
1 6 8样例输出
10样例说明
选择 1 月 3 日和 1 月 6 日的票据
评测用例规模与约定
对于 100% 的评测用例,1≤N≤1000,1≤M≤5000,1≤K≤50,1≤mi≤ 12,1≤di≤31,1≤vi≤400
日期保证合法。
运行限制
最大运行时间1s最大运行内存: 512M
总通过次数: 441 | 总提交次数: 513 | 通过率: 86%
难度: 简单 标签: 2022, 国赛, 01背包
#includeiostream
#includealgorithm
using namespace std;
int main()
{int N, M, K;cin N M K;int day[] { 0,31,59,90,120,151,181,212,243,273,304,334 };int dp[366];for (int i 0; i 366; i){dp[i] 0;}dp[0] 0;for (int i 0; i N; i){int m, d, v;cin m d v;dp[day[m - 1] d] max(dp[day[m-1]d],v);}for (int i 1; i 365; i){if (dp[i] dp[max(i - K, 0)] M)dp[i] max(dp[i] dp[max(i - K, 0)], dp[i - 1]);elsedp[i] dp[i - 1];}cout dp[365] endl;}
