PERKET

题目描述

Perket 是一种流行的美食。为了做好 Perket，厨师们必须小心选择配料，以便达到更好的口感。你有N种可支配的配料。对于每一种配料，我们知道它们各自的酸度 SS 和甜度 BB。当我们添加配料时，总的酸度为每一种配料的酸度总乘积；总的甜度为每一种配料的甜度的总和。

众所周知，美食应该口感适中；所以我们希望选取配料，以使得酸度和甜度的绝对差最小。

另外，我们必须添加至少一种配料，因为没有美食是以白水为主要配料的。

输入格式
第一行包括整数 NN，表示可支配的配料数。

接下来 NN 行，每一行为用空格隔开的两个整数，表示每一种配料的酸度和甜度。

输入数据保证，如果我们添加所有配料，总的酸度和甜度都不会超过 10^9 。

输出格式
输出酸度和甜度的最小的绝对差。

思路

嗯，这道题的话第一眼看用dfs因该就可以了。

首先审题，注意一下总的酸度为每一种配料的酸度总乘积，总的甜度为每一种配料的甜度的总和。

先上代码

using namespace std;
int n=0;
int bs[5][15];
//n为配料个数，bs为配料的酸度甜度（第一个是酸甜度，第二个是编号.舍弃下标0，下标1为酸，下标2为甜）
bool s[15]={0};
//配料是否使用
int ranks[15]={0};
//存放选好的配料编号
int l=1000000005;
//最大值
void dfs(int sel,int x){//x是要选的数if(sel==x){//如果c是0，代表选完了，int s=1;for(int i=1;i<=x;i++){s*=bs[1][ranks[i]];}int b=0;for(int i=1;i<=x;i++){b+=bs[2][ranks[i]];}if(abs(s-b)<l){l=abs(s-b);}}else{for(int i=1;i<=n;i++){if(!s[i]){ranks[sel+1]=i;s[i]=true;dfs(sel+1,x);s[i]=false;//注意恢复数组哟！}}}
}
int main(){cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=2;j++){cin>>bs[j][i];//输入}}for(int i=1;i<=n;i++)//这里用for循环来代表选取材料的数量{dfs(0,i);		}cout<<l;return 0;
}

注意点

1.绝对值函数

头文件：stdlib.h和math.h

2.恢复数组

s[i]=true;
dfs(sel+1,x);
s[i]=false;

记得在使用完后回复数组，方便下次使用。