婚纱摄影网站模板之家,网站建设建材,cdn wordpress 回复,电脑版cad免费怎么下载题目
Perket是一种流行的美食。为了做好Perket#xff0c;厨师必须谨慎选择食材#xff0c;以在保持传统风味的同时尽可能获得最全面的味道。你有n种可支配的配料。对于每一种配料#xff0c;我们知道它们各自的酸度s和苦度b。当我们添加配料时#xff0c;总的酸度为每一种…题目
Perket是一种流行的美食。为了做好Perket厨师必须谨慎选择食材以在保持传统风味的同时尽可能获得最全面的味道。你有n种可支配的配料。对于每一种配料我们知道它们各自的酸度s和苦度b。当我们添加配料时总的酸度为每一种配料的酸度总乘积总的苦度为每一种配料的苦度的总和。
众所周知美食应该做到口感适中所以我们希望选取配料以使得酸度和苦度的绝对差最小。
另外我们必须添加至少一种配料因为没有任何食物以水为配料的。
输入输出格式
输入格式
第一行一个整数n表示可供选用的食材种类数。
接下来n行每行2个整数si和bi表示第i种食材的酸度和苦度。
输出格式
一行一个整数表示可能的总酸度和总苦度的最小绝对差。
输入输出样例
输入样例
4
1 7
2 6
3 8
4 9
输出样例
1
代码
这个题目同样是DFS的经典题目。
#includeiostream
#includecmath
using namespace std;
int n,s[11],b[11],f[11];
int c1,y0,ans1000000;
void dfs(int x){if(xn){return;}else{for(int i1;in;i){if(f[i]0){c*s[i];yb[i];ansmin(ans,abs(c-y));f[i]1;dfs(x1);f[i]0;c/s[i];y-b[i];//搜索回溯 }}}
}
int main(){cinn;for(int i1;in;i){cins[i]b[i];}dfs(1);coutans;
}
