简答题
偏难
#20214
调味平衡 时间限制:1 s,内存限制:512 MB 【问题描述】 小 A 准备了 n 种食材用来制作料理,这些食材依次以 1、2、……、n 编号,第 i 种食材…
调味平衡
时间限制:1 s,内存限制:512 MB
【问题描述】
小 A 准备了 n 种食材用来制作料理,这些食材依次以 1、2、……、n 编号,第 i 种食材的酸度为 ai,甜度为 bi。
对于每种食材,小 A 可以选择将其放入料理,或者不放入料理。料理的酸度 A 为放入食材的酸度之和,甜度 B 为放入食材的甜度之和。如果料理的酸度与甜度相等,那么料理的调味是平衡的。
过于清淡的料理并不好吃,因此小 A 想在满足料理调味平衡的前提下,合理选择食材,最大化料理的酸度与甜度之和。
你能帮他求出在调味平衡的前提下,料理酸度与甜度之和的最大值吗?
【输入描述】
第一行,一个正整数 n,表示食材种类数量。
接下来 n 行,每行两个正整数 ai、bi,表示食材的酸度与甜度。
【输出描述】
输出共一行,一个整数,表示在调味平衡的前提下,料理酸度与甜度之和的最大值。
【样例输入1】
【样例输出1】
【样例输入2】
【样例输出2】
【数据范围】
对于40%的测试点,保证 1 <= n <= 10,1 <= ai、bi <= 10。
对于另外20%的测试点,保证 1 <= n <= 50,1 <= ai、bi <= 10。
对于所有测试点,保证 1 <= n <= 100,1 <= ai、bi <= 500。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <iostream>
using namespace std;
const int N = 105;
const int C = 505;
const int D = N * C * 2;
int n, f[D];
int main() {
cin >> n;
for (int i = 0; i < D; i++)
f[i] = -1e9;
f[N * C] = 0;
while (n--) {
int a, b;
cin >> a >> b;
int x = a + b, y = a - b;
if (y <= 0) {
for (int i = -y; i < D; i++)
f[i + y] = max(f[i + y], f[i] + x);
} else {
for (int i = D - y - 1; i; i--)
f[i + y] = max(f[i + y], f[i] + x);
}
}
cout << f[N * C] << endl;
return 0;
}</pre>
这道题暂未补解析。