题目来源：中山纪念中学

题目描述：

佳肴就是非常美味的菜的意思，佳肴最关键的是选择好原料。

现在有N种原料，每种原料都有酸度S和苦度B两个属性，当选择多种原料时，总酸度为每种原料的酸度之积，总苦度为每种原料的苦度之和。

正如大家所知，佳肴是既不酸也不苦的，因为要保证所选的原料使得总酸度和总苦度差的绝对值最小。

由于佳肴不能只有水，所以必须至少选择一种佳肴。

输入：

输入第一行包含一个整数N（1<=N<=10），表示原料的种数。
接下来N行每行包含两个用一个空格隔开的整数，分别表示酸度和苦度。
输入数据保证如果所有原料都选上，总酸度和总苦度不会超过10^9。

输出：

输出总酸度和总苦度最小的差。

输入样例：

输入1：
1
3 10

输入2：
2
3 8
5 8

输入3：
4
1 7
2 6
3 8
4 9

输出样例：

输出1：
7

输出2：
1

输出3：
1

样例解释：

样例3中选择最后三种原料，这样总酸度为2×3×4=24，总苦度为6+8+9=23，差为1。

思路：

n<=10是认真的吗？好玩 萌生了邪恶 的想法

以下代码请大佬们选择性食用☟

AC代码1：

#include<bits/stdc++.h>
using namespace std;
int n;
struct kind{
    long long sour;
    long long bit;
}a[11];
int main()
{
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i].sour>>a[i].bit;
    if (n==1) {cout<<abs(a[1].sour-a[1].bit)<<endl; return 0;}
    if (n==2) {cout<<min(min(abs(a[1].sour-a[1].bit),abs(a[2].sour-a[2].bit)),abs(a[1].sour*a[2].sour-(a[1].bit+a[2].bit))); return 0;}
    if (n==3)
    {
        long long a1=abs(a[1].sour-a[1].bit);
        long long a2=min(min(abs(a[1].sour-a[1].bit),abs(a[2].sour-a[2].bit)),abs(a[1].sour*a[2].sour-(a[1].bit+a[2].bit)));
        long long a3=99999999999;
        for (int i=1;i<=n;i++)
          for (int j=i+1;j<=n;j++)
            for (int k=j+1;k<=n;k++)
            {
                long long s=a[i].sour*a[j].sour*a[k].sour;
                long long b=a[i].bit+a[j].bit+a[k].bit;
                a3=min(a3,abs(s-b));
            }
        cout<<min(min(a1,a2),a3)<<endl;
        return 0;
    } 
    if (n==4)
    {
        long long a1=99999999999,a2=99999999999,a3=99999999999,a4=99999999999;
        for (int i=1;i<=n;i++)
        {
            a1=min(a1,abs(a[i].sour-a[i].bit));
          for (int j=i+1;j<=n;j++)
          {
            a2=min(a2,abs(a[i].sour*a[j].sour-(a[i].bit+a[j].bit)));
            for (int k=j+1;k<=n;k++)
            {
                long long s=a[i].sour*a[j].sour*a[k].sour;
                long long b=a[i].bit+a[j].bit+a[k].bit;
                a3=min(a3,abs(s-b));
             for (int p=k+1;p<=n;p++)
            {
                long long s=a[i].sour*a[j].sour*a[k].sour*a[p].sour;
                long long b=a[i].bit+a[j].bit+a[k].bit+a[p].bit;
                a4=min(a4,abs(s-b));
            }
            }
          }
          }
        cout<<min(min(min(a1,a2),a3),a4);
        return 0;
    }
    if (n==5)
    {
        long long a1=99999999999,a2=99999999999,a3=99999999999,a4=99999999999,a5=99999999999;
        for (int i=1;i<=n;i++)
        {
            a1=min(a1,abs(a[i].sour-a[i].bit));
          for (int j=i+1;j<=n;j++)
          {
            a2=min(a2,abs(a[i].sour*a[j].sour-(a[i].bit+a[j].bit)));
            for (int k=j+1;k<=n;k++)
            {
                long long s3=a[i].sour*a[j].sour*a[k].sour;
                long long b3=a[i].bit+a[j].bit+a[k].bit;
                a3=min(a3,abs(s3-b3));
            for (int p=k+1;p<=n;p++)
            {
                long long s4=a[i].sour*a[j].sour*a[k].sour*a[p].sour;
                long long b4=a[i].bit+a[j].bit+a[k].bit+a[p].bit;
                a4=min(a4,abs(s4-b4));
            for (int x=p+1;x<=n;x++)
            {
                long long s5=a[i].sour*a[j].sour*a[k].sour*a[p].sour*a[x].sour;
                long long b5=a[i].bit+a[j].bit+a[k].bit+a[p].bit+a[x].bit;
                a5=min(a5,abs(s5-b5));
            }
            }
            }
            }
        }
        cout<<min(min(min(min(a1,a2),a3),a4),a5);
        return 0;
    }
    if (n==6)
    {
        long long a6=99999999999,a1=99999999999,a2=99999999999,a3=99999999999,a4=99999999999,a5=99999999999;
        for (int i=1;i<=n;i++)
        {
            a1=min(a1,abs(a[i].sour-a[i].bit));
          for (int j=i+1;j<=n;j++)
          {
            a2=min(a2,abs(a[i].sour*a[j].sour-(a[i].bit+a[j].bit)));
            for (int k=j+1;k<=n;k++)
            {
                long long s3=a[i].sour*a[j].sour*a[k].sour;
                long long b3=a[i].bit+a[j].bit+a[k].bit;
                a3=min(a3,abs(s3-b3));
            for (int p=k+1;p<=n;p++)
            {
                long long s4=a[i].sour*a[j].sour*a[k].sour*a[p].sour;
                long long b4=a[i].bit+a[j].bit+a[k].bit+a[p].bit;
                a4=min(a4,abs(s4-b4));
            for (int x=p+1;x<=n;x++)
            {
                long long s5=a[i].sour*a[j].sour*a[k].sour*a[p].sour*a[x].sour;
                long long b5=a[i].bit+a[j].bit+a[k].bit+a[p].bit+a[x].bit;
                a5=min(a5,abs(s5-b5));
            for (int y=x+1;y<=n;y++)
            {
                long long s6=a[i].sour*a[j].sour*a[k].sour*a[p].sour*a[x].sour;
                long long b6=a[i].bit+a[j].bit+a[k].bit+a[p].bit+a[x].bit;
                a6=min(a6,abs(s6-b6));
            }
            }
            }
            }
        }
        }
        cout<<min(min(min(min(min(a1,a2),a3),a4),a5),a6);
        return 0;
    }
    if (n==7)
    {
        long long a7=99999999999,a6=99999999999,a1=99999999999,a2=99999999999,a3=99999999999,a4=99999999999,a5=99999999999;
        for (int i=1;i<=n;i++)
        {
            a1=min(a1,abs(a[i].sour-a[i].bit));
          for (int j=i+1;j<=n;j++)
          {
            a2=min(a2,abs(a[i].sour*a[j].sour-(a[i].bit+a[j].bit)));
            for (int k=j+1;k<=n;k++)
            {
                long long s3=a[i].sour*a[j].sour*a[k].sour;
                long long b3=a[i].bit+a[j].bit+a[k].bit;
                a3=min(a3,abs(s3-b3));
            for (int p=k+1;p<=n;p++)
            {
                long long s4=a[i].sour*a[j].sour*a[k].sour*a[p].sour;
                long long b4=a[i].bit+a[j].bit+a[k].bit+a[p].bit;
                a4=min(a4,abs(s4-b4));
            for (int x=p+1;x<=n;x++)
            {
                long long s5=a[i].sour*a[j].sour*a[k].sour*a[p].sour*a[x].sour;
                long long b5=a[i].bit+a[j].bit+a[k].bit+a[p].bit+a[x].bit;
                a5=min(a5,abs(s5-b5));
            for (int y=x+1;y<=n;y++)
            {
                long long s6=a[i].sour*a[j].sour*a[k].sour*a[p].sour*a[x].sour*a[y].sour;
                long long b6=a[i].bit+a[j].bit+a[k].bit+a[p].bit+a[x].bit+a[y].bit;
                a6=min(a6,abs(s6-b6));
            for (int z=y+1;z<=n;z++)
            {
                long long s7=a[i].sour*a[j].sour*a[k].sour*a[p].sour*a[x].sour*a[y].sour;
                long long b7=a[i].bit+a[j].bit+a[k].bit+a[p].bit+a[x].bit+a[y].bit;
                a7=min(a7,abs(s7-b7));  
            }
            }
            }
            }
            }
        }
        }
        cout<<min(min(min(min(min(min(a1,a2),a3),a4),a5),a6),a7);
        return 0;
    }
    if (n==8)
    {
        long long a8=99999999999,a7=99999999999,a6=99999999999,a1=99999999999,a2=99999999999,a3=99999999999,a4=99999999999,a5=99999999999;
        for (int i=1;i<=n;i++)
        {
            a1=min(a1,abs(a[i].sour-a[i].bit));
          for (int j=i+1;j<=n;j++)
          {
            a2=min(a2,abs(a[i].sour*a[j].sour-(a[i].bit+a[j].bit)));
            for (int k=j+1;k<=n;k++)
            {
                long long s3=a[i].sour*a[j].sour*a[k].sour;
                long long b3=a[i].bit+a[j].bit+a[k].bit;
                a3=min(a3,abs(s3-b3));
            for (int p=k+1;p<=n;p++)
            {
                long long s4=a[i].sour*a[j].sour*a[k].sour*a[p].sour;
                long long b4=a[i].bit+a[j].bit+a[k].bit+a[p].bit;
                a4=min(a4,abs(s4-b4));
            for (int x=p+1;x<=n;x++)
            {
                long long s5=a[i].sour*a[j].sour*a[k].sour*a[p].sour*a[x].sour;
                long long b5=a[i].bit+a[j].bit+a[k].bit+a[p].bit+a[x].bit;
                a5=min(a5,abs(s5-b5));
            for (int y=x+1;y<=n;y++)
            {
                long long s6=a[i].sour*a[j].sour*a[k].sour*a[p].sour*a[x].sour*a[y].sour;
                long long b6=a[i].bit+a[j].bit+a[k].bit+a[p].bit+a[x].bit+a[y].bit;
                a6=min(a6,abs(s6-b6));
            for (int z=y+1;z<=n;z++)
            {
                long long s7=a[i].sour*a[j].sour*a[k].sour*a[p].sour*a[x].sour*a[y].sour;
                long long b7=a[i].bit+a[j].bit+a[k].bit+a[p].bit+a[x].bit+a[y].bit;
                a7=min(a7,abs(s7-b7));  
            for (int d=z+1;d<=n;d++)
            {
                long long s8=a[i].sour*a[j].sour*a[k].sour*a[p].sour*a[x].sour*a[y].sour*a[d].sour;
                long long b8=a[i].bit+a[j].bit+a[k].bit+a[p].bit+a[x].bit+a[y].bit+a[d].bit;
                a8=min(a8,abs(s8-b8));
            }
            }
            }
            }
            }
            }
        }
        }
        cout<<min(min(min(min(min(min(min(a1,a2),a3),a4),a5),a6),a7),a8);
        return 0;
    }
    if (n==9)
    {
        long long a9=99999999999,a8=99999999999,a7=99999999999,a6=99999999999,a1=99999999999,a2=99999999999,a3=99999999999,a4=99999999999,a5=99999999999;
        for (int i=1;i<=n;i++)
        {
            a1=min(a1,abs(a[i].sour-a[i].bit));
          for (int j=i+1;j<=n;j++)
          {
            a2=min(a2,abs(a[i].sour*a[j].sour-(a[i].bit+a[j].bit)));
            for (int k=j+1;k<=n;k++)
            {
                long long s3=a[i].sour*a[j].sour*a[k].sour;
                long long b3=a[i].bit+a[j].bit+a[k].bit;
                a3=min(a3,abs(s3-b3));
            for (int p=k+1;p<=n;p++)
            {
                long long s4=a[i].sour*a[j].sour*a[k].sour*a[p].sour;
                long long b4=a[i].bit+a[j].bit+a[k].bit+a[p].bit;
                a4=min(a4,abs(s4-b4));
            for (int x=p+1;x<=n;x++)
            {
                long long s5=a[i].sour*a[j].sour*a[k].sour*a[p].sour*a[x].sour;
                long long b5=a[i].bit+a[j].bit+a[k].bit+a[p].bit+a[x].bit;
                a5=min(a5,abs(s5-b5));
            for (int y=x+1;y<=n;y++)
            {
                long long s6=a[i].sour*a[j].sour*a[k].sour*a[p].sour*a[x].sour*a[y].sour;
                long long b6=a[i].bit+a[j].bit+a[k].bit+a[p].bit+a[x].bit+a[y].bit;
                a6=min(a6,abs(s6-b6));
            for (int z=y+1;z<=n;z++)
            {
                long long s7=a[i].sour*a[j].sour*a[k].sour*a[p].sour*a[x].sour*a[y].sour;
                long long b7=a[i].bit+a[j].bit+a[k].bit+a[p].bit+a[x].bit+a[y].bit;
                a7=min(a7,abs(s7-b7));  
            for (int d=z+1;d<=n;d++)
            {
                long long s8=a[i].sour*a[j].sour*a[k].sour*a[p].sour*a[x].sour*a[y].sour*a[d].sour;
                long long b8=a[i].bit+a[j].bit+a[k].bit+a[p].bit+a[x].bit+a[y].bit+a[d].bit;
                a8=min(a8,abs(s8-b8));
            for (int e=d+1;e<=n;e++)
            {
                long long s9=a[i].sour*a[j].sour*a[k].sour*a[p].sour*a[x].sour*a[y].sour*a[d].sour*a[e].sour;
                long long b9=a[i].bit+a[j].bit+a[k].bit+a[p].bit+a[x].bit+a[y].bit+a[d].bit+a[e].bit;
                a9=min(a9,abs(s9-b9));
            }
            }
            }
            }
            }
            }
            }
        }
        }
        cout<<min(min(min(min(min(min(min(min(a1,a2),a3),a4),a5),a6),a7),a8),a9);
        return 0;
    }
    if (n==10)
    {
        long long a10=99999999999,a9=99999999999,a8=99999999999,a7=99999999999,a6=99999999999,a1=99999999999,a2=99999999999,a3=99999999999,a4=99999999999,a5=99999999999;
        for (int i=1;i<=n;i++)
        {
            a1=min(a1,abs(a[i].sour-a[i].bit));
          for (int j=i+1;j<=n;j++)
          {
            a2=min(a2,abs(a[i].sour*a[j].sour-(a[i].bit+a[j].bit)));
            for (int k=j+1;k<=n;k++)
            {
                long long s3=a[i].sour*a[j].sour*a[k].sour;
                long long b3=a[i].bit+a[j].bit+a[k].bit;
                a3=min(a3,abs(s3-b3));
            for (int p=k+1;p<=n;p++)
            {
                long long s4=a[i].sour*a[j].sour*a[k].sour*a[p].sour;
                long long b4=a[i].bit+a[j].bit+a[k].bit+a[p].bit;
                a4=min(a4,abs(s4-b4));
            for (int x=p+1;x<=n;x++)
            {
                long long s5=a[i].sour*a[j].sour*a[k].sour*a[p].sour*a[x].sour;
                long long b5=a[i].bit+a[j].bit+a[k].bit+a[p].bit+a[x].bit;
                a5=min(a5,abs(s5-b5));
            for (int y=x+1;y<=n;y++)
            {
                long long s6=a[i].sour*a[j].sour*a[k].sour*a[p].sour*a[x].sour*a[y].sour;
                long long b6=a[i].bit+a[j].bit+a[k].bit+a[p].bit+a[x].bit+a[y].bit;
                a6=min(a6,abs(s6-b6));
            for (int z=y+1;z<=n;z++)
            {
                long long s7=a[i].sour*a[j].sour*a[k].sour*a[p].sour*a[x].sour*a[y].sour;
                long long b7=a[i].bit+a[j].bit+a[k].bit+a[p].bit+a[x].bit+a[y].bit;
                a7=min(a7,abs(s7-b7));  
            for (int d=z+1;d<=n;d++)
            {
                long long s8=a[i].sour*a[j].sour*a[k].sour*a[p].sour*a[x].sour*a[y].sour*a[d].sour;
                long long b8=a[i].bit+a[j].bit+a[k].bit+a[p].bit+a[x].bit+a[y].bit+a[d].bit;
                a8=min(a8,abs(s8-b8));
            for (int e=d+1;e<=n;e++)
            {
                long long s9=a[i].sour*a[j].sour*a[k].sour*a[p].sour*a[x].sour*a[y].sour*a[d].sour*a[e].sour;
                long long b9=a[i].bit+a[j].bit+a[k].bit+a[p].bit+a[x].bit+a[y].bit+a[d].bit+a[e].bit;
                a9=min(a9,abs(s9-b9));
            for (int f=e+1;f<=n;f++)
            {
                long long s10=a[i].sour*a[j].sour*a[k].sour*a[p].sour*a[x].sour*a[y].sour*a[d].sour*a[e].sour*a[f].sour;
                long long b10=a[i].bit+a[j].bit+a[k].bit+a[p].bit+a[x].bit+a[y].bit+a[d].bit+a[e].bit+a[f].bit;
                a10=min(a10,abs(s10-b10));
            }
            }
            }
            }
            }
            }
            }
            }
        }
        }
        cout<<min(min(min(min(min(min(min(min(min(a1,a2),a3),a4),a5),a6),a7),a8),a9),a10);
        return 0;
    }
}

回归正题

既然数据这么小，直接搜索就行，不用剪枝也可以过

AC代码2：

#include<bits/stdc++.h>
using namespace std;
int n,anss=999999999;
struct kind{
    int sour;//酸度 
    int bit;//苦度 
}a[100];
void dg(int x,int s,int b,int k) //x代表菜肴种类，s代表酸度，b代表苦度，k代表这个菜肴选不选 
{
    if (x>n)   //递归到底了 
    {
        if(!k) return; //这个菜肴不选的话直接return 
        anss=min(anss,abs(s-b)); //答案要选取最小的度差 
        return;
    }
    dg(x+1,s,b,k);  //不选，直接下一个菜肴 
    dg(x+1,s*a[x].sour,b+a[x].bit,1); //选，酸度和苦度更新 
}
int main()
{
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i].sour>>a[i].bit;
    dg(1,1,0,0);
    cout<<anss<<endl;
    return 0;
}