Description
有两个长度为 $n$ 的数组 $s[]$ 和 $b[]$ 。
现在有一个长度为 $n$ 的并且只含有 0 和 1 并且至少有一个 $1$ 的数组 $k[]$ ，使得 $|\prod_{i=1}^{n}s_ik_i-\sum_{i=1}^{n}b_ik_i|$ 的值最小。
现在请你求出这个最小值。
$1\leq n\leq 10,\prod_{i=1}^{n}s_i,\sum_{i=1}^{n}b_i\leq 10^{9}$ 。
Solution
考虑使用 DFS 来解题。
由于 $1 \leq n \leq 10$ ，直接 DFS 选择即可。
时间复杂度 $O(2^{n})$ ，具体细节见 代码 部分。
然后这道题目就做完了。
Code
1 | #include<cmath>
|
2 | #include<cstdio>
|
3 | #include<cstring>
|
4 | #include<iostream>
|
5 | #include<algorithm>
|
6 | using namespace std;
|
7 | long long int n,a[11],b[11],ans=2147483647;
|
8 | void dfs(long long int nx,long long int an,long long int bn)
|
9 | {
|
10 | if(nx==n)
|
11 | {
|
12 | ans=min(ans,abs(an-bn));
|
13 | return;
|
14 | }
|
15 | dfs(nx+1,an,bn);
|
16 | dfs(nx+1,an*a[nx+1],bn+b[nx+1]);
|
17 | }
|
18 | int main()
|
19 | {
|
20 | scanf("%lld",&n);
|
21 | for(long long int i=1;i<=n;i++)
|
22 | {
|
23 | scanf("%lld%lld",&a[i],&b[i]);
|
24 | }
|
25 | for(long long int i=1;i<=n;i++)
|
26 | {
|
27 | dfs(i,a[i],b[i]);
|
28 | }
|
29 | printf("%lld",ans);
|
30 | return 0;
|
31 | }
|
