NOIP2016 Day2 T3(状压DP/DFS)

$n$小,搜索或者状压。
设$g(i, j)$为$i$和$j$组成一条抛物线的可被射的鸟的状态,$dp(S)$为在$S$状态时的最优解,然后转移就是
$$dp(S) = min(dp(S-g(i,j))+1)$$
初始化$g(i, j)$需要用待定系数法求出抛物线,即解二元一次方程,这个推一推就能推出通解了,复杂度$O(n^3)$
然后DP求解的时候是$O(2^nn^2)​$,有一点大,所以会TLE了几个点,有空补补$O(2^nn)​$做法

搜索做法:
设$g(i, j)$为$i$和$j$组成一条抛物线的可被射的鸟的状态,然后DFS,加可行性剪枝
DFS里每次看正在搜索的点是否已经被前面打了,用二进制优化,不然就和后面的相连或者一炮只打这一只小鸟,然后更新答案即可,这样做是满分的

2017.09.03: 搜索剪枝满分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 18 + 1;
const double eps = 1e-12;
void jfc(double &x, double &y, double a, double b, double c, double d, double e, double f) {
//ax+by=e
//cx+dy=f
if ((a * d - c * b) == 0 || a == 0) {x = 1, y = 1; return;}
y = (a * f - c * e) / (a * d - c * b);
x = (e - b * y) / a;
}
int n, m, p[MAXN][MAXN], f[MAXN][1 << MAXN], ans;
db xi[MAXN], yi[MAXN];
void dfs(int a, int st, int used) {
if (a == n + 1) {
ans = min(ans, used);
return ;
}
if (used >= ans) return ;
if (used >= f[a][st]) return ;
f[a][st] = used;
if (st >> (a - 1) & 1) dfs(a + 1, st, used); else {
for (int i = a + 1; i <= n; i++) {
dfs(a + 1, st | p[a][i], used + 1);
}
dfs(a + 1, st, used + 1);
}
}
void clean() {
ans = 1000000000;
ms(p, 0), ms(f, 127);
}
void solve() {
scanf("%d%d", &n, &m);
clean();
for (int i = 1; i <= n; i++) {
scanf("%lf%lf", &xi[i], &yi[i]);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) continue;
p[i][j] = (1 << (i - 1));
db nowx, nowy;
jfc(nowx, nowy, xi[i] * xi[i], xi[i], xi[j] * xi[j], xi[j], yi[i], yi[j]);
if (nowx >= 0) continue;
p[i][j] += (1 << (j - 1));
for (int k = 1; k <= n; k++) {
if (k != i && k != j) {
db orzx, orzy;
jfc(orzx, orzy, xi[i] * xi[i], xi[i], xi[k] * xi[k], xi[k], yi[i], yi[k]);
if (fabs(orzx - nowx) <= eps && fabs(orzy - nowy) <= eps) p[i][j] += (1 << (k - 1));
}
}
}
}
dfs(1, 0, 0);
printf("%d\n", ans);
}
int main() {
int t; scanf("%d", &t);
while (t--) solve();
return 0;
}

$O(2^nn^2)$做法(状压):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;
const int MAXN = 18 + 2;
const double eps = 0.000000001;
int n, m, g[MAXN][MAXN], dp[1<<MAXN];
double xi[MAXN], yi[MAXN];
void jfc(double &x, double &y, double a, double b, double c, double d, double e, double f) {
//ax+by=e
//cx+dy=f
if ((a*d-c*b)==0||a==0) {x = 1, y = 1; return;}//除0会炸
y = (a*f-c*e)/(a*d-c*b);
x = (e-b*y)/a;
}
void clean() {
ms(g, 0), ms(dp, 67);
}
__attribute__((optimize("-O2")))
void solve() {
scanf("%d%d", &n, &m);
clean();
for (int i=1;i<=n;i++) scanf("%lf%lf", &xi[i], &yi[i]);
for (int i=1;i<=n;i++) {
for (int j=i;j<=n;j++) if (!g[i][j]) {
double x, y;
if (i==j) {g[i][j] = (1<<(i-1)); continue;}//特判一下一个点
jfc(x, y, xi[i]*xi[i], xi[i], xi[j]*xi[j], xi[j], yi[i], yi[j]);
if (x>=0) continue;
g[i][j] = (1<<(i-1));
g[i][j] += (1<<(j-1));
for (int k=1;k<=n;k++)
if (i!=k&&j!=k) {
double dx, dy;
jfc(dx, dy, xi[i]*xi[i], xi[i], xi[k]*xi[k], xi[k], yi[i], yi[k]);
if (dx>=0) continue;
if (fabs(dx-x)<=eps&&fabs(dy-y)<=eps) g[i][j] += (1<<(k-1));
}
g[j][i] = g[i][j];
}
}
dp[0] = 0;
for (int S=1;S<(1<<n);S++) {
if (S==(1<<n)-1)
dp[0] = dp[0];
for (int i=1;i<=n;i++) {
if (S&(1<<(i-1))) {
for (int j=1;j<=n;j++) {
if ((S&(1<<(j-1)))&&((S&g[i][j])==g[i][j])) {
dp[S] = min(dp[S], dp[S^g[i][j]]+1);
}
}
}
}
}
printf("%d\n", dp[(1<<n)-1]);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
int T; scanf("%d", &T);
while (T--) solve();
return 0;
}

------ 本文结束 ------