周至做网站,网站建设中文摘要是什么,Pk10网站建设多少钱,南昌做网站kaiuP8803 [蓝桥杯 2022 国 B] 费用报销 分析
最值问题——DP
题意分析#xff1a;从N张票据中选#xff0c;且总价值不超过M的票据的最大价值#xff08;背包问题#xff09; K天限制
一、处理K天限制#xff1a;
1.对于输入的是月 日的格式#xff0c;很常用的方式是…P8803 [蓝桥杯 2022 国 B] 费用报销 分析
最值问题——DP
题意分析从N张票据中选且总价值不超过M的票据的最大价值背包问题 K天限制
一、处理K天限制
1.对于输入的是月 日的格式很常用的方式是将每个月的天数打表便于比较
2.对于第 i 张票据可选那么选的上一张即第 i - 1张票据的日期应该在第 i 张的前K天
具体做法将每张票据给出的日期转换为在这一年中的天数准备一个前缀和数组s[]记录第一个月到第i个月的天数日期m,d s[m] d
二、本题具体解法
1.背包问题的分析准备一个数组f[i][j]从前 i 个物品中选且总价值不超过 j 的最大价值任一f[i][j]都有选或不选两种选择不选f[i][j] f[i-1][j]选的话f[i][j]只能从与其时间间隔大于K天的票据中选所以
2.对天数进行排序准备一个数组op[]保存距离第 i 张票据最近且间隔天数大于K天的票据编号在DP中作为不选的方程来源f[i][j] f[op[i]][j-v]v
代码
#includeiostream
#includecstring
#includealgorithm
using namespace std;const int N 1010,M 5010;
struct tickets{int m,d,v,t;
}p[N];
int op[N],n,m,k,s[13],f[N][M];
//打表
int day[13] {0,31,28,31,30,31,30,31,31,30,31,30,31};//按天数排序
bool cmp(tickets a,tickets b)
{return a.t b.t;
}int main()
{//月份前缀和for(int i 2;i 13;i ) s[i] s[i - 1] day[i - 1];scanf(%d %d %d,n,m,k);for(int i 1;i n;i ){int m,d,v;scanf(%d %d %d,m,d,v);p[i].m m;p[i].d d;p[i].v v;p[i].t s[m] d;}//对天数排序sort(p 1,p n 1,cmp);//找到与i间隔大于等于K天且距离最近的点for(int i 1;i n;i ){for(int j 0;j i;j ){if(p[i].t - p[j].t k) op[i] j;}}//DP背包问题模板for(int i 1;i n;i ){for(int j m;j p[i].v;j --){//f[i][j] f[i - 1][j]; 滚动数组优化f[i][j] max(f[i-1][j],f[op[i]][j-p[i].v] p[i].v);}}printf(%d,f[n][m]);return 0;
}
