题解：洛谷 P13018 [GESP202506 七级] 调味平衡

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P13018 [GESP202506 七级] 调味平衡 - 洛谷【题目描述】小 A 准备了n nn种食材用来制作料理这些食材依次以1 , 2 , … , n 1,2,\dots,n1,2,…,n编号第i ii种食材的酸度为a i a_iai​甜度为b i b_ibi​。对于每种食材小 A 可以选择将其放入料理或者不放入料理。料理的酸度A AA为放入食材的酸度之和甜度B BB为放入食材的甜度之和。如果料理的酸度和甜度相等那么料理的调味是平衡的。过于清淡的料理并不好吃因此小 A 想在满足料理调味平衡的前提下合理选择食材最大化料理的酸度与甜度之和。你能帮他求出在调味平衡的前提下料理酸度与甜度之和的最大值吗【输入】第一行一个正整数n nn表示食材种类数量。接下来n nn行每行两个正整数a i , b i a_i,b_iai​,bi​表示食材的酸度和甜度。【输出】输出共一行一个整数表示在调味平衡的前提下料理酸度与甜度之和的最大值。【输入样例】3 1 2 2 4 3 2【输出样例】8【算法标签】#普及【代码详解】#includeiostream#includecstringusingnamespacestd;constintN105,M1000005;// 定义最大物品数N和最大容量Mintn,f[N][M],d[N],s[N];// 物品数nDP数组f差值数组d和值数组sintmain(){memset(f,-0x3f3f3f,sizeoff);// 初始化DP数组为极小值cinn;// 输入物品数量f[0][50000]0;// 初始化基础状态偏移量50000for(inti1;in;i)// 读取每个物品的数据{inta,b;// 物品的两个属性cinab;// 输入a和bd[i]a-b;// 计算差值s[i]ab;// 计算和值}for(inti1;in;i)// 遍历每个物品{for(intjd[i];j100000;j)// 遍历所有可能的容量{f[i][j]max(f[i-1][j],f[i-1][j-d[i]]s[i]);// 状态转移方程}}coutf[n][50000];// 输出结果return0;// 程序正常结束}【运行结果】3 1 2 2 4 3 2 8