简答题 偏难
#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】

3
1 2
2 4
3 2

【样例输出1】

8

【样例输入2】

5
1 1
2 3
6 1
8 2
5 7

【样例输出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 &lt;iostream&gt; using namespace std; const int N = 105; const int C = 505; const int D = N * C * 2; int n, f[D]; int main() {     cin &gt;&gt; n;     for (int i = 0; i &lt; D; i++)         f[i] = -1e9;     f[N * C] = 0;     while (n--) {         int a, b;         cin &gt;&gt; a &gt;&gt; b;         int x = a + b, y = a - b;         if (y &lt;= 0) {             for (int i = -y; i &lt; 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 &lt;&lt; f[N * C] &lt;&lt; endl;     return 0; }</pre>
这道题暂未补解析。