P2036——PERKET

这里是原题链接P2036

这道题难度不大，大概意思就是输入一个数n，让你输入n个配料，每个配料有两种属性分别为酸和苦，配料的使用中酸是累乘的，而苦是累加的，让你在这n个配料选出几个使得酸和苦的差值最小

首先想到的是使用搜索算法，数据范围不大，n最多也就取10。然后注意到，我们的搜索的层数是不确定的，我们可以选择一个配料，也可以选择n个配料，但最后要找出差值最小的那一个数，所以我们可以使用IDA*算法，搜索的过程中每个结点的信息应该有当前的总酸度，总苦度，还有当前选择了几个配料=


以下是代码，具体含义都在代码说明了

#include <iostream>
#include <math.h>
#include <algorithm>using namespace std;
int s[11], b[11], maxd, ans=0x3fffffff, n;
bool vis[11];void dfs(int step,int nows,int nowb)//step当前使用的配料个数，nows当前的总酸度，nowb当前的总苦度
{
    if(step==maxd){
    ans = min(abs(nows - nowb), ans);return;}for (int i = 1; i <= n; i++){
    if(vis[i]==true)//如果该配料使用过了，跳到下一个continue;vis[i]=true;dfs(step + 1, nows * s[i], nowb + b[i]);//不然选择这一个配料并且更新数值vis[i]=false;//回溯}return;
}int main() {
    cin >> n;for (int i = 1; i <= n; i++){
    cin >> s[i] >> b[i];}for (maxd = 1; maxd <= n; maxd++){
    //maxd表示选择配料个数的最大值dfs(0, 1, 0);}cout << ans << endl;return 0;
}

需要注意的是，因为酸度是采用累乘的方式，我们搜索的时候要设置为1
每个配料只能使用一次，所以我们设一个vis数组来表示第i个配料是否使用过