当前位置：首页 > news >正文

题解：AtCoder AT_awc0062_c Optimal Menu Selection for an Izakaya

news 2026/5/6 17:39:22

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

AtCoder：C - 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 DD
A 1 A_1A1B 1 B_1B1
A 2 A_2A2B 2 B_2B2
⋮ \vdots⋮
A N A_NANB N B_NBN

The 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 ) (N+1)(N+1)-th line, the deliciousness and richness of each dish are given.
The( 1 + i ) (1+i)(1+i)-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

【输出样例】

【算法标签】

#状压DP#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong// 将int定义为long long类型constintN=25,M=1<<20;// N:最大物品数(25), M:最大子集数(2^20)intn;// 物品数量intk;// 脂肪标准值intd;// 脂肪惩罚系数intans;// 最大满意度inta[N];// 存储每个物品的美味值intb[N];// 存储每个物品的脂肪值intsuma[M];// 子集的美味值总和intsumb[M];// 子集的脂肪值总和signedmain()// 因为使用了#define int long long，所以用signed{cin>>n>>k>>d;// 输入物品数量、脂肪标准值、惩罚系数// 输入每个物品的美味值和脂肪值for(inti=1;i<=n;i++){cin>>a[i]>>b[i];}// 预处理：计算所有子集的美味值总和和脂肪值总和for(intmask=1;mask<(1<<n);mask++)// mask表示物品子集{intlsb=__builtin_ctz(mask);// 获取mask的最低有效位（从0开始）intprevMask=mask^(1<<lsb);// 去掉最低有效位suma[mask]=suma[prevMask]+a[lsb+1];// 计算美味值总和sumb[mask]=sumb[prevMask]+b[lsb+1];// 计算脂肪值总和}// 遍历所有子集，计算最大满意度for(intmask=0;mask<(1<<n);mask++){intdelicious=suma[mask];// 当前子集的美味值总和intrich=sumb[mask];// 当前子集的脂肪值总和// 计算满意度：美味值总和 - 脂肪惩罚intsatisfaction=delicious-d*max(0LL,rich-k);ans=max(ans,satisfaction);// 更新最大满意度}cout<<ans<<endl;// 输出最大满意度return0;// 程序正常结束}