本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AtCoderC - Optimal Menu Selection for an Izakaya【题目描述】Takahashi is at an izakaya (Japanese-style pub). The menu hasN NNdishes, and thei ii-th dish has a “deliciousness” valueA i A_iAiand a “richness” valueB i B_iBi. Takahashi can order any combination of these dishes. Each dish can be ordered at most once, and it is also allowed to order no dishes at all (in which case, the satisfaction is0 00).高桥在一家居酒屋。菜单上有N NN道菜第i ii道菜有一个美味度值A i A_iAi和一个浓郁度值B i B_iBi。高桥可以点任意组合的这些菜。每道菜最多点一次也可以不点任何菜此时满意度为0 00。Takahashi likes rich dishes, but if the total richness of the ordered dishes exceedsK KK, his satisfaction decreases byD DDfor each unit of excess richness.高桥喜欢浓郁的菜但如果所点菜品的总浓郁度超过K KK他的满意度会降低每超出1 11单位扣除D DD的满意度。Specifically, Takahashi’s final satisfaction is calculated by the following formula:具体来说高桥的最终满意度由以下公式计算Satisfaction ( Total deliciousness of ordered dishes ) − D × max ( 0 , Total richness of ordered dishes − K ) \text{Satisfaction} \left(\text{Total deliciousness of ordered dishes}\right) - D \times \max\!\left(0,\ \text{Total richness of ordered dishes} - K\right)Satisfaction(Total deliciousness of ordered dishes)−D×max(0,Total richness of ordered dishes−K)满意度 ( 所点菜品的美味度总和 ) − D × max ( 0 , 所点菜品的总浓郁度 − K ) \text{满意度} \left(\text{所点菜品的美味度总和}\right) - D \times \max\!\left(0,\ \text{所点菜品的总浓郁度} - K\right)满意度(所点菜品的美味度总和)−D×max(0,所点菜品的总浓郁度−K)Find the maximum satisfaction Takahashi can achieve.求高桥能获得的最大满意度。【输入】N NNK KKD DDA 1 A_1A1B 1 B_1B1A 2 A_2A2B 2 B_2B2⋮ \vdots⋮A N A_NANB N B_NBNThe first line contains the number of dishesN NN, the richness tolerance limitK KK, and the satisfaction decrease per unit of excessD DD, separated by spaces.From the 2nd line to the( N 1 ) (N1)(N1)-th line, the deliciousness and richness of each dish are given.The( 1 i ) (1i)(1i)-th line contains the deliciousnessA i A_iAiand richnessB i B_iBiof thei ii-th dish, separated by a space.【输出】Print the maximum satisfaction Takahashi can achieve as an integer on a single line.【输入样例】3 5 2 4 2 5 3 10 6【输出样例】9【算法标签】#状压DP#【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglong// 将int定义为long long类型constintN25,M120;// N:最大物品数(25), M:最大子集数(2^20)intn;// 物品数量intk;// 脂肪标准值intd;// 脂肪惩罚系数intans;// 最大满意度inta[N];// 存储每个物品的美味值intb[N];// 存储每个物品的脂肪值intsuma[M];// 子集的美味值总和intsumb[M];// 子集的脂肪值总和signedmain()// 因为使用了#define int long long所以用signed{cinnkd;// 输入物品数量、脂肪标准值、惩罚系数// 输入每个物品的美味值和脂肪值for(inti1;in;i){cina[i]b[i];}// 预处理计算所有子集的美味值总和和脂肪值总和for(intmask1;mask(1n);mask)// mask表示物品子集{intlsb__builtin_ctz(mask);// 获取mask的最低有效位从0开始intprevMaskmask^(1lsb);// 去掉最低有效位suma[mask]suma[prevMask]a[lsb1];// 计算美味值总和sumb[mask]sumb[prevMask]b[lsb1];// 计算脂肪值总和}// 遍历所有子集计算最大满意度for(intmask0;mask(1n);mask){intdelicioussuma[mask];// 当前子集的美味值总和intrichsumb[mask];// 当前子集的脂肪值总和// 计算满意度美味值总和 - 脂肪惩罚intsatisfactiondelicious-d*max(0LL,rich-k);ansmax(ans,satisfaction);// 更新最大满意度}coutansendl;// 输出最大满意度return0;// 程序正常结束}【运行结果】3 5 2 4 2 5 3 10 6 9
