Luogu P2831 愤怒的小鸟

题目链接

一个搜索,或者状压,蒟蒻不会状压dp,就写了搜索。。。


  • 一个猪,有两种方式死,一是只被一只鸟打死,另外一个是和之前一只猪一起被同一只鸟打死,因为两只猪确定一条抛物线。

  • 然后搜索其实就是对于第i个猪,到目前为止已经确定了ok条抛物线,还有no个没有组成抛物线的猪(就是独自被一只鸟打死的),然后看一下之前已经组成的抛物线有没有一条能够打死该猪,可以的话就往后搜就行,不然就分两种情况:

    1. 这只猪和这只猪之前的一只猪组成一条抛物线。

    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
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
using namespace std;

int n, m, ans;
int maxn;
struct node{
double x, y;
}a[20];
struct node1{
double a, b;
}p[20];
bool vis[20];

bool sam(double a, double b){
return abs(a - b) <= 1e-6;
}

void dfs(int k, int ok, int no){
if(k == n + 1){
ans = min(ans, ok + no);
}
if(ok + no >= ans) return;
//这个地方一定得注意,上面这句写>=是最优性剪枝。
//一定得写>=,写>会超时,T一个点。
//下面一定得>,因为会WA。。。
if(ok + no > maxn) return;
int flag = 1;
for(int i = 1; i <= ok; i++){
if(sam(p[i].a*a[k].x*a[k].x+p[i].b*a[k].x, a[k].y)){
//这里处理了第一种情况,就是能和之前已经有的抛物线组成一起。
//然后vis数组这个比较正常。
vis[k] = 1;
dfs(k + 1, ok, no);
vis[k] = 0;
flag = 0;
break;
}
}
if(flag){
//这里处理第二种情况,与这个猪前面其中一个猪组成一条抛物线。
for(int i = 1; i < k; i++){
if(vis[i]) continue;
if(a[i].x == a[k].x) continue;
//这里计算一下aa和bb,就是抛物线的a和b,拿方程组手推一下就出来了。
double aa = (a[k].y*a[i].x/a[k].x-a[i].y)/(a[i].x*(a[k].x-a[i].x));
double bb = (a[k].y-aa*a[k].x*a[k].x)/a[k].x;
if(aa < 0){
p[ok+1].a = aa;
p[ok+1].b = bb;
vis[i] = 1;
vis[k] = 1;
dfs(k + 1, ok + 1, no - 1);
vis[i] = 0;
vis[k] = 0;
}
}
//最后这里是第三种情况,就是这一个单独组成一个抛物线。。。
dfs(k + 1, ok, no + 1);
}
}

int main(){
int T;
scanf("%d", &T);
while(T--){
ans = 0x3f3f3f3f;
maxn = 0x3f3f3f3f;
memset(vis, 0, sizeof(vis));
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++){
double x, y;
scanf("%lf%lf", &x, &y);
a[i].x = x;
a[i].y = y;
}
if(m == 1) maxn = ceil(n / 3.0 + 1);
dfs(1, 0, 0);
printf("%d\n", ans);
}
return 0;
}
# 搜索

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×