[COCI2008-2009 #2] PERKET
题目描述
Perket 是一种流行的美食。为了做好 Perket,厨师必须谨慎选择食材,以在保持传统风味的同时尽可能获得最全面的味道。你有 $n$ 种可支配的配料。对于每一种配料,我们知道它们各自的酸度 $s$ 和苦度 $b$。当我们添加配料时,总的酸度为每一种配料的酸度总乘积;总的苦度为每一种配料的苦度的总和。
众所周知,美食应该做到口感适中,所以我们希望选取配料,以使得酸度和苦度的绝对差最小。
另外,我们必须添加至少一种配料,因为没有任何食物以水为配料的。
输入格式
第一行一个整数 $n$,表示可供选用的食材种类数。
接下来 $n$ 行,每行 $2$ 个整数 $s_i$ 和 $b_i$,表示第 $i$ 种食材的酸度和苦度。
输出格式
一行一个整数,表示可能的总酸度和总苦度的最小绝对差。
样例 #1
样例输入 #1
1
3 10
样例输出 #1
7
样例 #2
样例输入 #2
2
3 8
5 8
样例输出 #2
1
样例 #3
样例输入 #3
4
1 7
2 6
3 8
4 9
样例输出 #3
1
提示
数据规模与约定
对于 $100\%$ 的数据,有 $1 \leq n \leq 10$,且将所有可用食材全部使用产生的总酸度和总苦度小于 $1 \times 10^9$,酸度和苦度不同时为 $1$ 和 $0$。
说明
- 本题满分 $70$ 分。
- 题目译自 COCI2008-2009 CONTEST #2 PERKET,译者 @mnesia。
题解
卡住了 做的时候我还以为会稳稳拿捏 结果发现根本不会对酸度和苦度进行全排列
因为一个是前缀和 一个是前缀积 你没有办法先将每一个数据预处理 你也没有排列的依据
我不知道该怎么枚举子集
现在还做不出来 先放这了 万一以后明白了
放一个写了一半的代码
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int a[N]; //酸度前缀积
int b[N]; //苦度前缀和
int n;
int ans = 0x3f3f3f3f;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
{
int l, k;
scanf("%d%d", &l, &k);
a[i] = a[i - 1] * l;
b[i] = b[i - 1] + k;
}
for (int i = 1; i <= n; i ++ )
{
for (int j = i + 1; j <= n; j ++ )
{
if (i == 1)
ans = abs((b[j] - b[i - 1])- (a[j] / a[i - 1]));
else
ans = min(ans, abs((b[j] - b[i - 1])- (a[j] / a[i - 1]));
}
for (int j = n; j > i; j -- )
{
if (i == 1)
ans = abs((b[j] - b[i - 1])- (a[j] / a[i - 1]));
else
ans = min(ans, abs((b[j] - b[i - 1])- (a[j] / a[i - 1]));
}
}
}
dfs做法
深搜就能很轻而易举的实现我所说的枚举所有子集的情况
比如有 1 2 3 4 当我选上配料1我想跳过2去找3和4配料 在dfs里我就只需要通过dfs(i + 1, x, y)
来实现
就是维持上一配料留下的酸度积和苦度和 直接去搜下一个配料
太妙了
关键点 当我们搜索到这个编号的时候有两种选择 添加这个配料 或者 不添加这个配料直接往下搜索 这就是我在做枚举的时候想实现的!
dfs(i + 1, x * a[i], y + b[i]);
dfs(i + 1, x, y);
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int a[N]; //酸度
int b[N]; //苦度
int n;
int ans = 0x3f3f3f3f;
void dfs(int i, int x, int y) //i表示当前配料编号 x表示目前酸度积 y表示目前苦度和
{
if (i > n) //只有当把目前所有编号遍历完之后 才能进入找酸度积和苦度和相减的绝对值 的最小值
{
if (x == 1 && y == 0) return; //这是清水的情况
else
{
ans = min(ans, abs(x - y));
return;
}
}
//关键点 当我们搜索到这个编号的时候有两种选择 添加这个配料 或者 不添加这个配料直接往下搜索 这就是我在做枚举的时候想实现的!
dfs(i + 1, x * a[i], y + b[i]);
dfs(i + 1, x, y);
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d%d", &a[i], &b[i]);
dfs(1, 1, 0); //注意这里有一个坑点 一定要把酸度的搜索初始值写成1 酸度是以乘积的形式实现的 初值为0 相乘就一直为0
printf("%d\n", ans);
return 0;
}