题目描述
此题主要思路y总已经在视频中讲解过,整个题目思路不难,主要分为二次函数预处理以及重复覆盖问题两大部分。但是写起来十分容易错,细节很多。我花了将近一上午的时间用记忆化搜索的方法和状压dp的方法分别重写了这道题。从结果来看,记忆化搜索(100ms)比状压dp(754ms)要更快,主要得益于记忆化搜索可以避免搜索点很多不必要的状态,这个从后面代码中可以看出。此题需要注意的点主要有以下几点:
1.path[i][i]必须要初始化,否则后面在更新state的时候会出现问题
2.题目要求a < 0 因此a >= 0的情况要予以消除
3.x1 == x2的情况要予以排除
4.浮点数比较要用cmp
5.如果是使用同一个数组,每次循环后需要重新memset用到的数组
6.如果不用记忆化搜索此题会超时!
7.运算符优先级 加减 > 位运算 > 等于 > 与
path[i][j]表示经过i和j号小猪的抛物线能够攻打的小猪编号的二进制组合,如path[4][5] = 110101 中0,2, 4,5号位为1,因此通过4号小猪和5号小猪的抛物线能够攻打到0,2,4,5号小猪
在状压dp中,f[state] 表示从开始状态到当前状态state所需要的最少的小鸟数量,如state的二进制表示为11111,表示所有小猪都没有被攻打到0,1,2,3,4号小猪被攻打所需要的小鸟最小数量的,因此f[(1<<n)-1]为最终结果。
在记忆化搜索中,f[state]表示从state到所有小猪都被打完需要的最少小鸟数量,如state的二进制表示为00000,表示从所有小猪都没有攻打到所有小猪都被攻打所需要的最少小鸟数量,因此dfs(0)为最终结果。
状态转移方程:f[state | path[i][k]] = min(f[state | path[i][k]], f[state] + 1)
具体实现细节见算法1和算法2
算法1
(记忆化搜索)
因为记忆化搜索不会搜索到0 - ((1 << n) - 1)之中的所有状态,即使会调用较多的栈帧,但在本题的样例中,记忆化搜索的用时会比状压dp更少。
时间复杂度
未知(用时100ms)
C++ 代码
#include <bits/stdc++.h>
using namespace std;
struct pig {
double x, y;
} p[20];
int n, m;
int path[20][20];
int f[1<<18];
int cmp(double a, double b) {
if (fabs(a - b) < 1e-6) return 0;
if (a > b) return 1;
return -1;
}
void init(int i, int j) {
double x1 = p[i].x, y1 = p[i].y;
double x2 = p[j].x, y2 = p[j].y;
if (!cmp(x1, x2)) return;
double a = (y1 / x1 - y2 / x2) / (x1 - x2);
if (a >= 0) return;
double b = y1 / x1 - a * x1;
for (int k = 0; k < n; k++) {
double t = a * p[k].x * p[k].x + b * p[k].x;
if (!cmp(t, p[k].y))
path[i][j] |= (1 << k);
}
}
int dfs(int state) {
if (state == (1 << n) - 1) return 0;
if (f[state]) return f[state];
// 找到任意一个state为0的元素
int x;
for (int i = 0; i < n; i++)
if ((state >> i & 1) == 0) {
x = i;
break;
}
// 找到一个包含x的列进行覆盖
int res = INT_MAX;
for (int i = 0; i < n; i++) {
// 排除掉path[x][i]不包含任何子集的情况
if (path[x][i] != 0)
res = min(dfs(state|path[x][i]) + 1, res) ;
}
f[state] = res;
return res;
}
int main() {
int T;
cin >> T;
while (T--) {
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> p[i].x >> p[i].y;
for (int i = 0; i < n; i++) {
path[i][i] = 1 << i;
for (int j = 0; j < n; j++)
init(i, j);
}
cout << dfs(0) << endl;
// 恢复现场
for (int i = 0; i < 1 << n; i++)
f[i] = 0;
memset(path, 0, sizeof path);
}
return 0;
}
算法2
(状压dp)
时间复杂度
$O(n^3+n*2^n)$ 用时754ms
C++ 代码
#include <bits/stdc++.h>
using namespace std;
struct pig {
double x, y;
} p[20];
int n, m;
int path[20][20];
int f[1<<18];
int cmp(double a, double b) {
if (fabs(a - b) < 1e-6) return 0;
if (a > b) return 1;
return -1;
}
void init(int i, int j) {
double x1 = p[i].x, y1 = p[i].y;
double x2 = p[j].x, y2 = p[j].y;
if (!cmp(x1, x2)) return;
double a = (y1 / x1 - y2 / x2) / (x1 - x2);
if (a >= 0) return;
double b = y1 / x1 - a * x1;
for (int k = 0; k < n; k++) {
double t = a * p[k].x * p[k].x + b * p[k].x;
if (!cmp(t, p[k].y))
path[i][j] |= (1 << k);
}
}
int main() {
int T;
cin >> T;
while (T--) {
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> p[i].x >> p[i].y;
for (int i = 0; i < n; i++) {
path[i][i] = 1 << i;
for (int j = 0; j < n; j++)
init(i, j);
}
memset(f, 0x3f, sizeof f);
f[0] = 0;
int x = 0;
for (int state = 0; state < 1 << n; state++) {
for (int j = 0; j < n; j++)
if (!(state >> j & 1)) {
x = j;
break;
}
for (int j = 0; j < n; j++)
f[state | path[x][j]] = min(f[state | path[x][j]], f[state] + 1);
}
cout << f[(1 << n) - 1] << endl;
memset(path, 0, sizeof path);
}
return 0;
}
初始化
path[i][i]
的原因是某些点可能是独立的(不能与其它点形成抛物线,那么他们需要被任意一条过它自己的抛物线覆盖,即初始化path[i][i] = 1 << i
记忆化搜索为什么不是 状态到state==(1<<n) - 1的时候,输出答案呢,而是答案是dfs0呢,还是2种写法都可以
for (int i = 0; i < n; i++)
if ((state >> i & 1) == 0) {
x = i;
break;
}
为什么只要找到一个未覆盖的点进行就可以,而不是从每个未覆盖的点
我也想知道啊啊啊啊啊·
懂了吗( ̄∀ ̄)
洛谷上这道题有解析
覆盖的顺序并不重要,只需要覆盖每个未覆盖点点即可。
记忆化搜索比视频更好理解,支持!
我也觉得,点赞支持
感谢支持!
这个才是好题解