A27106. 调味平衡
填空题
困难
知识点
题目描述
调味平衡
题目描述
小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。
参考答案
#include <cstdio>
#include <algorithm>
using namespace std;
const int N= 105;
const int C=505;
const int D=N*C*2;
int n;
int f[D];
int main(){
scanf("%d"，&n);
for(int i=0;i<D; i++)
f[i]= -1e9;
f[N * C]= 0;
while(n--){
int a, b;
scanf("%d%d"，&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);
}
}
printf("%d\n",f[N * C]);
return 0;
}
上一题
下一题