本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AtCoderC - Reward for Carrying Luggage【题目描述】There areN NNrooms arranged in a row, numbered Room1 11, Room2 22,… \ldots…, RoomN NNfrom left to right. Takahashi visits these rooms one by one in order from Room1 11to RoomN NN, and for each room, he chooses to either “accept” or “decline” the job offered there. Each room has exactly one job, and he visits each room exactly once.Each roomi iihas a job with typeT i T_iTiand rewardA i A_iAi. There are two types of jobs:Loading job(T i 1 T_i 1Ti1): If accepted, he receives rewardA i A_iAiand picks up one piece of luggage. The number of pieces of luggage he is carrying increases by1 11.Unloading job(T i 0 T_i 0Ti0): If accepted, he receives rewardA i A_iAi. If he is carrying one or more pieces of luggage, he puts down one piece, and the number of pieces of luggage he is carrying decreases by1 11. If he is carrying no luggage, there is nothing to put down, so the number of pieces of luggage remains0 00(he still receives the reward).The number of pieces of luggage Takahashi is carrying is initially0 00. Throughout the process of accepting and declining jobs,the number of pieces of luggage must not exceedK KKat any point. This is because carrying too much luggage would be unmanageable.Additionally,the number of pieces of luggage must be exactly0 00after visiting all rooms(because he cannot go home while still carrying luggage).Determine the maximum total reward of the jobs Takahashi accepts while satisfying these conditions. Note that it is possible to accept no jobs at all, in which case the total reward is0 00.有N NN个房间排成一行从左到右编号为房间1 11、房间2 22、……、房间N NN。高桥按顺序从房间1 11到房间N NN依次访问这些房间对于每个房间他选择接受或拒绝那里提供的工作。每个房间恰好有一份工作他恰好访问每个房间一次。每个房间i ii有一份类型为T i T_iTi、报酬为A i A_iAi的工作。有两种类型的工作装载工作T i 1 T_i 1Ti1如果接受他获得报酬A i A_iAi并拿起一件行李。他携带的行李件数增加1 11。卸载工作T i 0 T_i 0Ti0如果接受他获得报酬A i A_iAi。如果他正携带一件或更多件行李他放下一件行李携带的行李件数减少1 11。如果他没有携带任何行李就没有东西可放下因此行李件数保持为0 00他仍然获得报酬。高桥初始携带的行李件数为0 00。在接受和拒绝工作的整个过程中行李件数在任何时刻都不得超过K KK。这是因为携带太多行李会难以管理。此外访问完所有房间后行李件数必须恰好为0 00因为他不能还带着行李回家。确定在满足这些条件的情况下高桥接受的工作的最大总报酬。注意有可能不接受任何工作此时总报酬为0 00。【输入】N NNK KKT 1 T_1T1A 1 A_1A1T 2 T_2T2A 2 A_2A2⋮ \vdots⋮T N T_NTNA N A_NANThe first line contains the number of roomsN NNand the upper limit on the number of pieces of luggageK KK, separated by a space.From the 2nd line to the( N 1 ) (N 1)(N1)-th line, the job information for each room is given.The( 1 i ) (1 i)(1i)-th line contains the typeT i T_iTiof the job in roomi ii(1 11: loading,0 00: unloading) and the rewardA i A_iAi, separated by a space.【输出】Print in one line the maximum total reward of accepted jobs when choosing which jobs to accept while satisfying the conditions.【输入样例】4 1 1 5 0 4 1 3 0 10【输出样例】22【算法标签】#线性DP-一维【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN100005,INF-1e18;intn,k;// n: 天数k: 初始能量intt[N],a[N];// t[i]: 第i天的类型a[i]: 第i天的能量值vectorvectorintf;// DP数组signedmain(){cinnk;// 输入天数和初始能量intsum0;for(inti1;in;i)// 输入每天的类型和能量值{cint[i]a[i];}// 初始化f数组所有值初始化为-1e18f.assign(n1,vectorint(k1,INF));f[0][0]0;// 初始状态for(inti1;in;i)// 遍历每一天{for(intjk;j0;j--)// 遍历能量值{f[i][j]f[i-1][j];// 不选择第i天if(t[i]1)// 第i天是类型1{if(j1)// 能量值大于等于1f[i][j]max(f[i][j],f[i-1][j-1]a[i]);// 消耗1点能量获取a[i]}else// 第i天是类型2{if(j1k)// 能量值小于kf[i][j]max(f[i][j],f[i-1][j1]a[i]);// 增加1点能量获取a[i]f[i][0]max(f[i][0],f[i-1][0]a[i]);// 能量值为0时也可以获取a[i]}}}coutmax(0LL,f[n][0])endl;// 输出最后一天能量为0时的最大值return0;}【运行结果】4 1 1 5 0 4 1 3 0 10 22
题解：AtCoder AT_awc0080_c Reward for Carrying Luggage
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AtCoderC - Reward for Carrying Luggage【题目描述】There areN NNrooms arranged in a row, numbered Room1 11, Room2 22,… \ldots…, RoomN NNfrom left to right. Takahashi visits these rooms one by one in order from Room1 11to RoomN NN, and for each room, he chooses to either “accept” or “decline” the job offered there. Each room has exactly one job, and he visits each room exactly once.Each roomi iihas a job with typeT i T_iTiand rewardA i A_iAi. There are two types of jobs:Loading job(T i 1 T_i 1Ti1): If accepted, he receives rewardA i A_iAiand picks up one piece of luggage. The number of pieces of luggage he is carrying increases by1 11.Unloading job(T i 0 T_i 0Ti0): If accepted, he receives rewardA i A_iAi. If he is carrying one or more pieces of luggage, he puts down one piece, and the number of pieces of luggage he is carrying decreases by1 11. If he is carrying no luggage, there is nothing to put down, so the number of pieces of luggage remains0 00(he still receives the reward).The number of pieces of luggage Takahashi is carrying is initially0 00. Throughout the process of accepting and declining jobs,the number of pieces of luggage must not exceedK KKat any point. This is because carrying too much luggage would be unmanageable.Additionally,the number of pieces of luggage must be exactly0 00after visiting all rooms(because he cannot go home while still carrying luggage).Determine the maximum total reward of the jobs Takahashi accepts while satisfying these conditions. Note that it is possible to accept no jobs at all, in which case the total reward is0 00.有N NN个房间排成一行从左到右编号为房间1 11、房间2 22、……、房间N NN。高桥按顺序从房间1 11到房间N NN依次访问这些房间对于每个房间他选择接受或拒绝那里提供的工作。每个房间恰好有一份工作他恰好访问每个房间一次。每个房间i ii有一份类型为T i T_iTi、报酬为A i A_iAi的工作。有两种类型的工作装载工作T i 1 T_i 1Ti1如果接受他获得报酬A i A_iAi并拿起一件行李。他携带的行李件数增加1 11。卸载工作T i 0 T_i 0Ti0如果接受他获得报酬A i A_iAi。如果他正携带一件或更多件行李他放下一件行李携带的行李件数减少1 11。如果他没有携带任何行李就没有东西可放下因此行李件数保持为0 00他仍然获得报酬。高桥初始携带的行李件数为0 00。在接受和拒绝工作的整个过程中行李件数在任何时刻都不得超过K KK。这是因为携带太多行李会难以管理。此外访问完所有房间后行李件数必须恰好为0 00因为他不能还带着行李回家。确定在满足这些条件的情况下高桥接受的工作的最大总报酬。注意有可能不接受任何工作此时总报酬为0 00。【输入】N NNK KKT 1 T_1T1A 1 A_1A1T 2 T_2T2A 2 A_2A2⋮ \vdots⋮T N T_NTNA N A_NANThe first line contains the number of roomsN NNand the upper limit on the number of pieces of luggageK KK, separated by a space.From the 2nd line to the( N 1 ) (N 1)(N1)-th line, the job information for each room is given.The( 1 i ) (1 i)(1i)-th line contains the typeT i T_iTiof the job in roomi ii(1 11: loading,0 00: unloading) and the rewardA i A_iAi, separated by a space.【输出】Print in one line the maximum total reward of accepted jobs when choosing which jobs to accept while satisfying the conditions.【输入样例】4 1 1 5 0 4 1 3 0 10【输出样例】22【算法标签】#线性DP-一维【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN100005,INF-1e18;intn,k;// n: 天数k: 初始能量intt[N],a[N];// t[i]: 第i天的类型a[i]: 第i天的能量值vectorvectorintf;// DP数组signedmain(){cinnk;// 输入天数和初始能量intsum0;for(inti1;in;i)// 输入每天的类型和能量值{cint[i]a[i];}// 初始化f数组所有值初始化为-1e18f.assign(n1,vectorint(k1,INF));f[0][0]0;// 初始状态for(inti1;in;i)// 遍历每一天{for(intjk;j0;j--)// 遍历能量值{f[i][j]f[i-1][j];// 不选择第i天if(t[i]1)// 第i天是类型1{if(j1)// 能量值大于等于1f[i][j]max(f[i][j],f[i-1][j-1]a[i]);// 消耗1点能量获取a[i]}else// 第i天是类型2{if(j1k)// 能量值小于kf[i][j]max(f[i][j],f[i-1][j1]a[i]);// 增加1点能量获取a[i]f[i][0]max(f[i][0],f[i-1][0]a[i]);// 能量值为0时也可以获取a[i]}}}coutmax(0LL,f[n][0])endl;// 输出最后一天能量为0时的最大值return0;}【运行结果】4 1 1 5 0 4 1 3 0 10 22
