题解 P2036 【Perket】

Ash_Dr · 2020-03-09 22:15:37 · 题解

2020.4.8更新了LaTeX{}

蒟蒻来写自己的第一篇题解，求管理大大过啊QAQ 最近在深基上看完了枚举子集这一板块 来刷这道红题

看讨论区的大佬都在用DFS，但是本蒟蒻就想用枚举做(因为这是枚举板块的习题)

好的，废话不多说 看题

首先看一下数据范围，不愧是红题，数据范围十分的友好 n最多只有10，虽然枚举子集的复杂度是O(2^n)级别的，但这样的数据范围允许我们使用子集枚举

为什么想到子集枚举呢？(不难想到)其实这道题本质就是在这些调料中选择适当数目的调料来满足题目要求，自然也就是枚举整个调料集合的子集啦

现在介绍如何枚举子集
我们看这样一个二进制 (0110) 我们可以从右向左，当第几位出现了1，就代表a[i]在当前子集中，那么我们只需要枚举1\text{到}2^n-1 即可(具体细节实现读者可以自己画图仔细想想)

给上代码 注释在代码中

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int min(int x, int y ) {return x<y?x:y;}//自定义函数
int s[12],b[12];
int main() {
    int n;
    cin>>n;
    for(int i=0; i<n; i++) {
        cin>>s[i]>>b[i];
    }//注意从0开始存
    int u=1<<n;//对全集的处理，需要用到二进制知识
    int ans=99999999;
    for(int i=1; i<u; i++) {
        int ss=1,bb=0;//用来求积/和的变量
        for(int j=0; j<=n; j++) {//这一层循环用来判断当前数哪几位为1
            if(i&(1<<j)) {
                ss*=s[j];
                bb+=b[j];
            }
        }
        ans = min(ans,(int)abs(ss-bb));//判断
    }
    cout<<ans;

} //23ms 680kb