P2036 [COCI2008-2009#2] PERKET

野性酷女 2023-02-17 03:38 38阅读 0赞

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

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

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

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

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

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

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

输入输出样例  
输入 \#1复制  
1  
3 10

输出 \#1复制  
7  
输入 \#2复制  
4  
1 7  
2 6  
3 8  
4 9  
输出 \#2复制  
1  
说明/提示  
1\\le N\\le 1≤N≤10。  
解题思路：  
暴力枚举：即2N种可能，然后搜索出绝对值最小的。

#include<iostream>
    #include<algorithm>
    #include<cmath>
    #include<cstring>
    using namespace std;
    typedef long long ll;
    int n,ans=1e9;
    int a[12],b[12];
    void dfs(int cur,int s,int t)
    { 
    	if(cur>n)
    	{ 
    		if(s!=0)
    		ans=min(ans,abs(s-t));
    		return ;
    	}
    	for(int i=1;i<=2;i++)
    	{ 
    		if(i==1)//选第i+1件配料 
    		{ 
    			if(s==0)
    			dfs(cur+1,a[cur],t+b[cur]);
    			else
    			dfs(cur+1,s*a[cur],t+b[cur]);
    		}
    		else
    		{ 
    			dfs(cur+1,s,t);
    		}
    	}
    }
    int main()
    { 
       ios::sync_with_stdio(0),cin.tie(0);
       int i;
       cin>>n;
       for(i=1;i<=n;i++)
       cin>>a[i]>>b[i];
       dfs(0,0,0);
       cout<<ans;
       return 0;
    }

[Link 1]: https://www.luogu.com.cn/problem/P2036